[题解]NOI2005 维护数列

输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。

Solution

        这道题是Splay的模板题，但是很容易错。我调了好久，在除了bzoj之外的各大题库都AC了，只是在bzoj一直不明原因的RE。这道题要注意的是，它的MAX-SUM询问在整个序列为负的情况下答案应该是最大的复数而不是0，这个坑了我半天。标记要打好。这题由于最多会插入4000000个点，但最多同时在序列中有500000个，所以要开个内存池，重复利用开过的数组空间（如果用的是指针树那么没有必要）。

代码：

#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;#define lch T[T[x].ch[0]]
#define rch T[T[x].ch[1]]inline int read(){int x=0,f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';return x*f;
}const int maxn=500010,oo=0x7f7f7f7f;
struct node{int fa,ch[2],size,same,data,sum;int lmax,rmax,max;bool reverse;
}T[maxn];
int n,m,a[maxn],root,stack[maxn],top=0;void create(int x){T[stack[top]].data=x;T[stack[top]].same=oo;T[stack[top]].size=1;T[stack[top]].lmax=T[stack[top]].rmax=T[stack[top]].max=x;T[stack[top]].fa=T[stack[top]].reverse=T[stack[top]].ch[0]=T[stack[top]].ch[1]=0;top--;
}
void pushsame(int x,int c){if(!x)return;T[x].data=T[x].same=c;T[x].sum=c*T[x].size;T[x].lmax=T[x].rmax=T[x].max=max(T[x].sum,c);
}
void pushreverse(int x){if(!x)return;T[x].reverse^=1;swap(T[x].ch[0],T[x].ch[1]);swap(T[x].lmax,T[x].rmax);
}
void pushdown(int x){if(T[x].same!=oo){pushsame(T[x].ch[0],T[x].same);pushsame(T[x].ch[1],T[x].same);T[x].same=oo;}if(T[x].reverse){pushreverse(T[x].ch[0]);pushreverse(T[x].ch[1]);T[x].reverse=false;}
}
void upmax(int x){T[x].lmax=lch.sum+T[x].data+max(0,rch.lmax);if(T[x].ch[0])T[x].lmax=max(T[x].lmax,lch.lmax);T[x].rmax=rch.sum+T[x].data+max(0,lch.rmax);if(T[x].ch[1])T[x].rmax=max(T[x].rmax,rch.rmax);T[x].max=max(0,lch.rmax)+T[x].data+max(0,rch.lmax);if(T[x].ch[0])T[x].max=max(T[x].max,lch.max);if(T[x].ch[1])T[x].max=max(T[x].max,rch.max);
}
void update(int x){if(!x)return;T[x].size=1;T[x].sum=T[x].data;if(T[x].ch[0]){T[x].size+=lch.size;T[x].sum+=lch.sum;}if(T[x].ch[1]){T[x].size+=rch.size;T[x].sum+=rch.sum;}upmax(x);
}
int build(int l,int r,int fa){if(l>r)return 0;int mid=(l+r)>>1;create(a[mid]);int temp=stack[top+1];T[temp].fa=fa;T[temp].ch[0]=build(l,mid-1,temp);T[temp].ch[1]=build(mid+1,r,temp);update(temp);return temp;
}
int getson(int p){return p==T[T[p].fa].ch[1];
}
void rotate(int p){if(!T[p].fa)return;int k=getson(p),fa=T[p].fa;int fafa=T[fa].fa;pushdown(fa);pushdown(p);T[fa].ch[k]=T[p].ch[k^1];if(T[p].ch[k^1])T[T[p].ch[k^1]].fa=fa;T[p].ch[k^1]=fa;T[fa].fa=p;T[p].fa=fafa;if(fafa)T[fafa].ch[fa==T[fafa].ch[1]]=p;update(fa);update(p);update(fafa);
}
void Splay(int u,int f){for(int fa;(fa=T[u].fa)!=f;rotate(u)){if(T[fa].fa!=f){rotate((getson(fa)==getson(u))?fa:u);}}if(!f){root=u;update(f);}
}
int Rank(int x){int p=root;while(1){pushdown(p);if(T[p].ch[0]&&x<=T[T[p].ch[0]].size)p=T[p].ch[0];else{int temp=(T[p].ch[0]?T[T[p].ch[0]].size:0)+1;if(x==temp)return p;x-=temp;p=T[p].ch[1];}}
}
void rec(int x){if(!x)return;stack[++top]=x;rec(T[x].ch[0]);rec(T[x].ch[1]);
}
void Insert(int l,int nrt){int x=Rank(l),y=Rank(l+1);Splay(x,0);Splay(y,x);T[y].ch[0]=nrt;T[nrt].fa=y;update(y);update(x);
}
void Delete(int l,int r){int x=Rank(l-1),y=Rank(r+1);Splay(x,0);Splay(y,x);rec(T[y].ch[0]);T[y].ch[0]=0;update(y);update(x);
}
void Make_same(int l,int r,int c){int x=Rank(l-1),y=Rank(r+1);Splay(x,0);Splay(y,x);pushsame(T[y].ch[0],c);update(y);update(x);
}
void Reverse(int l,int r){int x=Rank(l-1),y=Rank(r+1);Splay(x,0);Splay(y,x);pushreverse(T[y].ch[0]);update(y);update(x);
}
int Get_sum(int l,int r){int x=Rank(l-1),y=Rank(r+1);Splay(x,0);Splay(y,x);return T[T[y].ch[0]].sum;
}
int Max_sum(int l,int r){int x=Rank(l-1),y=Rank(r+1);Splay(x,0);Splay(y,x);return T[T[y].ch[0]].max;
}
void Init(){for(int i=1;i<=maxn-5;i++)stack[++top]=i;n=read();m=read();for(int i=1;i<=n;i++)a[i]=read();root=build(0,++n,0);
}
void Work(){while(m--){string opt;int pos,tot;cin>>opt;if(opt=="INSERT"){pos=read();tot=read();for(int i=1;i<=tot;i++)a[i]=read();Insert(pos+1,build(1,tot,0));}else if(opt=="DELETE"){pos=read();tot=read();Delete(pos+1,pos+tot);}else if(opt=="MAKE-SAME"){pos=read();tot=read();int c=read();Make_same(pos+1,pos+tot,c);}else if(opt=="REVERSE"){pos=read();tot=read();Reverse(pos+1,pos+tot);}else if(opt=="GET-SUM"){pos=read();tot=read();printf("%d\n",Get_sum(pos+1,pos+tot));}else if(opt=="MAX-SUM"){pos=read();tot=read();printf("%d\n",Max_sum(pos+1,pos+tot));}else{int k=read();printf("%d\n",T[Rank(k+1)].data);}}
}int main(){Init();Work();return 0;
}