1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MB
Description
Input
输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。
Output
对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。
Sample Input
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
Sample Output
10
1
10
HINT
这次我们学习无旋treap的区间操作（如果没有了解过无旋treap，你可以选择查看我上一篇讲解博文[您有新的未分配科技点]无旋treap：从好奇到入门）
这道例题，真的是平衡树神题……
区间操作我们并没有见过，但我们可以联想一下单点操作时普通平衡树里都干了些什么：
"合并两棵树”和“把一棵树的前k个节点分裂出来”
可不可以用这些操作进行区间操作？显然是可以的，只要我们每次新建一棵树就可以了
在具体操作之前，我们先来看一下区间操作的原理：为什么平衡树的区间操作是对的？
我们知道，平衡树是一种二叉排序树，它的各种操作的前提是不会改变排序树的中序遍历
如果我们按照想要的中序遍历建树并且合并，我们一定能得到正确的区间，所以平衡树的区间操作是正确的。
这也是平衡树的两大建立方式之一：按中序遍历建树（另外一种是按权值建树……就是最常见的那种）
这样就涉及到一个没有出现的函数：build（建树）函数
build函数的原理和"笛卡尔树"的建造是比较像的（没有听说过笛卡尔树？请看笛卡尔树）
我们用下面一张图来简要讲解一下build的构造过程（注意，定义key为维护堆性质的随机键值）
假设这是我的无旋treap目前的状态，我用一个栈来维护这棵树最右边的一条链，并且每一次在右下角处插入节点
假设我此时我们在9的右儿子添加了一个13，若13的key值小于栈顶元素9的key，那么就开始退栈，停止退栈的条件有两个，满足任意一个即停止：
Treap *stack[N],*x,*last;
inline Treap *build()
{
int p=;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
x=newTreap(a[i]);last=null;
while(p&&stack[p]->key > x->key)
{stack[p]->update();last=stack[p];stack[p--]=null;}
if(p)stack[p]->ch[]=x;
x->ch[]=last;stack[++p]=x;
}
while(p)stack[p--]->update();
return stack[];
}
有了这个build操作，在加上之前的操作，我们很容易得出
insert=split+build+merge+merge
delete=split+split+merge
下面在考虑其他4个操作：
make-same：和线段树一样打标记并且下传就好
注意，这个操作会影响到最大连续和的求解，需要更新维护信息（更新谁请读者思考）。
reserve：这也是平衡树区间操作的经典考题……区间翻转问题
对于节点o，我们也是用一个标记来维护这个问题，
操作到这个节点时下传标记，然后用swap交换o的左右儿子即可。
不幸的是，这个操作也会影响到最大连续和的求解，也需要更新维护信息（更新谁请读者思考）。
get-sum：每个节点多维护一个sum附加值，在维护节点信息的时候更新即可。
get-max：这个操作也是一种经典的询问。
它需要我们多维护下面三个信息：最大前缀和，最大后缀和以及最大连续和。
对于每一个节点的最大前缀和，这个值可能是
1°它的左儿子的前缀和；
2°左儿子的和+它的val
3°左儿子的和+它的val+右儿子的前缀和
最大后缀和同理。
而最大连续和，这个范围可能完全在左儿子中，可能完全在右儿子中，也可能卡在左右儿子中间
所以我们可能的取值为：
1°左儿子的最大连续和；
2°右儿子的最大连续和
3°max（0，左儿子的后缀和）+它的val+max（右儿子的前缀和）
这样我们就解决了这个问题。觉得还是不太明白的同学可以去做一下cogs775山海经这道题，它就是单纯询问最大连续和一个操作。
这样，6个操作都被我们处理完了。本题不卡内存和时间，所以放心大胆的码就可以了……
代码见下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
using namespace std;
const int N=;
const int MAXN=;
const int inf=0x3f3f3f3f;
int n,a[N],point;
struct Treap
{
Treap *ch[];
int val,key,size,sum,l,r,m;bool flip,mark;
Treap(){val=l=r=m=-inf;sum=;size=;mark=flip=;key=rand();}
inline void update()
{
size=ch[]->size+ch[]->size+;
sum=val+ch[]->sum+ch[]->sum;
l=max(ch[]->l,max(ch[]->sum+val,ch[]->sum+val+ch[]->l));
r=max(ch[]->r,max(val+ch[]->sum,ch[]->r+val+ch[]->sum));
m=max(ch[]->m,max(max(,ch[]->r)+val+max(,ch[]->l),ch[]->m));
}
}*null=new Treap(),*root=null,*stack[N],*x,*last;
typedef pair<Treap*,Treap*> D;
inline void Maintain_flip(Treap *o)
{
if(o==null)return;
o->flip^=;swap(o->l,o->r);
}
inline void Maintain_mark(Treap *o,int c)
{
if(o==null)return;
o->val=c;o->sum=o->size*c;
o->l=o->r=o->m=max(o->size*c,c);
o->mark=;
}
inline void pushdown(Treap *o)
{
if(o==null)return;
if(o->flip)
{
o->flip^=;
Maintain_flip(o->ch[]);
Maintain_flip(o->ch[]);
swap(o->ch[],o->ch[]);
}
if(o->mark)
{
Maintain_mark(o->ch[],o->val);
Maintain_mark(o->ch[],o->val);
o->mark=;
}
}
inline Treap* newTreap(int val)
{
Treap *o=new Treap();
o->ch[]=o->ch[]=null;o->key=rand();
o->val=o->sum=val;o->size=;o->flip=o->mark=;
o->m=o->l=o->r=val;
return o;
}
Treap *merge(Treap *a,Treap *b)
{
if(a==null)return b;
if(b==null)return a;
pushdown(a);pushdown(b);
if(a->key < b->key)
{a->ch[]=merge(a->ch[],b);a->update();return a;}
else
{b->ch[]=merge(a,b->ch[]);b->update();return b;}
}
D split(Treap *o,int k)
{
if(o==null) return D(null,null);
D y;pushdown(o);
if(o->ch[]->size>=k)
{y=split(o->ch[],k);o->ch[]=y.second;o->update();y.second=o;}
else
{y=split(o->ch[],k-o->ch[]->size-);o->ch[]=y.first;o->update();y.first=o;}
return y;
}
inline Treap *build()
{
int p=;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
x=newTreap(a[i]);last=null;
while(p&&stack[p]->key > x->key)
{stack[p]->update();last=stack[p];stack[p--]=null;}
if(p)stack[p]->ch[]=x;
x->ch[]=last;stack[++p]=x;
}
while(p)stack[p--]->update();
return stack[];
}
void adjust(Treap *o)
{
if(o==null)return;
if(o->ch[]!=null)adjust(o->ch[]);
if(o->ch[]!=null)adjust(o->ch[]);
delete o;
}
inline void insert()
{
int pos;scanf("%d%d",&pos,&n);
Treap *o=build();
D x=split(root,pos);
root=merge(merge(x.first,o),x.second);
}
inline void erase()
{
int pos;scanf("%d%d",&pos,&n);
D x=split(root,pos-);
D y=split(x.second,n);
adjust(y.first);
root=merge(x.first,y.second);
}
inline void reverse()
{
int pos;scanf("%d%d",&pos,&n);
D x=split(root,pos-);
D y=split(x.second,n);
Maintain_flip(y.first);
root=merge(merge(x.first,y.first),y.second);
}
inline void make_same()
{
int pos,c;scanf("%d%d%d",&pos,&n,&c);
D x=split(root,pos-);
D y=split(x.second,n);
Maintain_mark(y.first,c);
root=merge(merge(x.first,y.first),y.second);
}
inline int get_sum()
{
int pos;scanf("%d%d",&pos,&n);
if(n==)return ;
D x=split(root,pos-);
D y=split(x.second,n);
int ret=y.first->sum;
root=merge(merge(x.first,y.first),y.second);
return ret;
}
int main()
{
int m;scanf("%d%d",&n,&m);root=build();
char opt[];
while(m--)
{
scanf("%s",opt);
switch(opt[])
{
case 'I':{insert();break;}
case 'D':{erase();break;}
case 'M':
{
if(opt[]=='K'){make_same();break;}
else {printf("%d\n",root->m);break;}
}
case 'G':{printf("%d\n",get_sum());break;}
case 'R':{reverse();break;}
}
}
}
BZOJ1500