[CC-STREETTA]The Street

摘要:
[CC-STRETTA]The Street主题的主要思想:给定两个长度序列的和,起始序列中每个项目的值为,序列中每个项的值为。第二个操作包括以下操作:将等差序列添加到序列间隔。对于数字序列,请使用Li Hypertree保持最大值。对于数字序列,直接合并两个分析表达式。
[CC-STREETTA]The Street

题目大意:

给定两个长度为(n(nle10^9))的数列(A)(B),开始数列(A)中每一项值为(-infty),数列(B)中每一项值为(0)(m(mle3 imes10^5))次操作,操作包含以下(3)种:

  1. 数列(A)区间加一条等差数列。
  2. 数列(B)区间对一个等差数列取(max)
  3. 询问(A_i+B_i)

思路:

每个结点维护一个解析式(kx+b)

对于数列(A),使用李超树维护最大值。

对于数列(B),直接合并两个解析式。

时间复杂度(mathcal O(mlog n))

源代码:

#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
	register char ch;
	register bool neg=false;
	while(!isdigit(ch=getchar())) neg|=ch=='-';
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return neg?-x:x;
} 
typedef long long int64;
const int SIZE=9e6;
struct Node {
	int64 a,b;
	void operator += (const Node &rhs) {
		a+=rhs.a;
		b+=rhs.b;
	}
};
int64 calc(const Node &s,const int &x) {
	return s.a*x+s.b;
}
class SegmentTree1 {
	#define mid ((b+e)>>1)
	private:
		Node node[SIZE];
		int left[SIZE],right[SIZE];
		int sz,new_node() {
			node[++sz]=(Node){0,LLONG_MIN};
			return sz;
		}
	public:
		int root;
		void modify(int &p,const int &b,const int &e,const int &l,const int &r,Node s) {
			p=p?:new_node();
			if(b==l&&e==r) {
				if(calc(node[p],b)<calc(s,b)) std::swap(node[p],s);
				if(calc(node[p],e)>=calc(s,e)) return;
				const double c=1.*(s.b-node[p].b)/(node[p].a-s.a);
				if(c<=mid) {
					modify(left[p],b,mid,b,mid,node[p]);
					node[p]=s;
				}
				if(c>mid) modify(right[p],mid+1,e,mid+1,e,s);
				return;
			}
			if(l<=mid) modify(left[p],b,mid,l,std::min(mid,r),s);
			if(r>mid) modify(right[p],mid+1,e,std::max(mid+1,l),r,s);
		}
		int64 query(int &p,const int &b,const int &e,const int &x) {
			p=p?:new_node();
			int64 ret=calc(node[p],x);
			if(b==e) return ret;
			if(x<=mid) ret=std::max(ret,query(left[p],b,mid,x));
			if(x>mid) ret=std::max(ret,query(right[p],mid+1,e,x));
			return ret;
		}
	#undef mid
};
SegmentTree1 t1;
class SegmentTree2 {
	#define mid ((b+e)>>1)
	private:
		Node node[SIZE];
		int left[SIZE],right[SIZE];
		int sz,new_node() {
			return ++sz;
		}
	public:
		int root;
		void modify(int &p,const int &b,const int &e,const int &l,const int &r,const Node &s) {
			p=p?:new_node();
			if(b==l&&e==r) {
				node[p]+=s;
				return;
			}
			if(l<=mid) modify(left[p],b,mid,l,std::min(mid,r),s);
			if(r>mid) modify(right[p],mid+1,e,std::max(mid+1,l),r,s);
		}
		int64 query(int &p,const int &b,const int &e,const int &x) {
			p=p?:new_node();
			int64 ret=calc(node[p],x);
			if(b==e) return ret;
			if(x<=mid) ret+=query(left[p],b,mid,x);
			if(x>mid) ret+=query(right[p],mid+1,e,x);
			return ret;
		}
	#undef mid
};
SegmentTree2 t2;
int main() {
	const int n=getint(),m=getint();
	for(register int i=0;i<m;i++) {
		const int opt=getint();
		if(opt==1) {
			const int u=getint(),v=getint(),a=getint(),b=getint();
			t1.modify(t1.root,1,n,u,v,(Node){a,b-(int64)u*a});
		}
		if(opt==2) {
			const int u=getint(),v=getint(),a=getint(),b=getint();
			t2.modify(t2.root,1,n,u,v,(Node){a,b-(int64)u*a});
		}
		if(opt==3) {
			const int i=getint();
			const int64 a=t1.query(t1.root,1,n,i),b=t2.query(t2.root,1,n,i);
			if(a==LLONG_MIN) {
				puts("NA");
			} else {
				printf("%lld
",a+b);
			}
		}
	}
	return 0;
}

免责声明:文章转载自《[CC-STREETTA]The Street》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Invoker(小DP)[CF115E]Linear Kingdom Races下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

CentOS 安装 epel repo const_yixinyiyi的日志 网易博客

CentOS 安装 epel repo - const_yixinyiyi的日志 - 网易博客 CentOS 安装 epel repo 2011-10-24 10:48:27|分类: Web |标签: |字号大中小订阅 Cent OS 使用EPEL, 用惯了Ubuntu 的 apt-get, 觉得非常方便, 在RHEL 里必须买服务才能用yu...

选择尽可能多的不相交区间

题目:有n个区间,[ai, bi), 统计不相交区间最多有多少个? 贪心策略:将这n个区间按bi由小到大排序,然后从前向后遍历,每当遇到不相交的区间就加入目标集合,遍历完成后就找到了最多的不相交区间。 正确性证明:参见http://blog.csdn.net/dgq8211/article/details/7534488 以下是HDUOJ2037的源代...

说说C#中的enum吧

enum,就是枚举类型,它是struct,int,single,double一样,都属于值类型,从ValueType类型中派生,存储在栈中。它在被创建时,不需要分配内在空间,所以对程序的性能是有好处的。 为啥要引入enum呢?一个原因,就是让程序更加安全,添加程序的可读性,提高开发的效率。 啥时用呢?当我们已经确定了变更的数量,功能时可以将变更一个个的枚举出...

flex扫盲篇

本人因项目需要,要做报表,项目初步用flex做,我还是应届生,连flex是什么东西都不知道,坑爹的,我花了大概一天的时间,完成flex和服务器的交互 首先要知道flex是做页面的美化的,flex与服务器交互有2个组件,一是httpservice 还有一个是remoteobject。 下面我把我的第一个flex程序交给大家,我会把我在做这个demo的时候碰到的...

NetBeans 时事通讯(刊号 # 54 May 01, 2009 )

刊号 # 54 - May 01, 2009 项目新闻 新的NetBeans模块和源代码可以得到了! NetBeans插件门户现在存放了新的由Tim Boudreau贡献的模块的集合。签出它们。它们的源代码也能够在NetBeans的代码仓库得到。 赢取$200的Zembly博客大赛吧! Zembly是一个用来构建Facebook,...

嵌入式设备的上下文感知电源管理框架(论文阅读笔记)

本文是一篇关于电源管理框架的论文阅读笔记【By CoryXie <cory.xie@gmail.com>】,虽然算不上原创,但也不是完全的翻译,因此勉强选择了这个类型。 原文:<A Framework for Context-Aware Power Management on Embedded Devices> 来源:http://...