1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 11047 Solved: 3460
[Submit][Status][Discuss]
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
9 8
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
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
-1
10
1
10
10
1
10
HINT
Source
Solution
splay模板题，exciting
插入和删除一个序列，有种方便快捷的方法
进行两次伸展，一次伸展到根，一次伸展到右子树上，这样会可以使得左子树空缺或需要删除是左子树
那么直接插入一整棵树到左子树，或者删除整个左子树即可
那么给定的序列，可以利用 线段树类似的build技巧，将其建成一个完美的二叉树，然后直接加入
BZOJ卡内存，所以删除的时候需要垃圾回收
具体的方法就是 使用一个队列，记录扔掉的点的编号，加入新东西时，先从队列中取编号，再建新编号即可
Code
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> using namespace std; int read() { int x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } #define maxn 1000100 queue<int>trashpool; int n,m,cnt; int fa[maxn],son[maxn][2],key[maxn],size[maxn],sum[maxn],val[maxn],maxz[maxn],ll[maxn],rr[maxn],id[maxn]; bool rev[maxn],tag[maxn]; int sz,root; void update(int now) { //if (!now) return; size[now]=size[son[now][0]]+size[son[now][1]]+1; sum[now]=val[now]+sum[son[now][0]]+sum[son[now][1]]; maxz[now]=max(maxz[son[now][0]],maxz[son[now][1]]); maxz[now]=max(maxz[now],rr[son[now][0]]+val[now]+ll[son[now][1]]); ll[now]=max(ll[son[now][0]],sum[son[now][0]]+val[now]+ll[son[now][1]]); rr[now]=max(rr[son[now][1]],sum[son[now][1]]+val[now]+rr[son[now][0]]); } void pushdown(int now) { int tg=tag[now],rv=rev[now]; if (tag[now]) { tag[now]=0; rev[now]=0; if (son[now][0]) tag[son[now][0]]=1,val[son[now][0]]=val[now],sum[son[now][0]]=size[son[now][0]]*val[now]; if (son[now][1]) tag[son[now][1]]=1,val[son[now][1]]=val[now],sum[son[now][1]]=size[son[now][1]]*val[now]; if(val[now]>=0) { if(son[now][0]) ll[son[now][0]]=rr[son[now][0]]=maxz[son[now][0]]=sum[son[now][0]]; if(son[now][1]) ll[son[now][1]]=rr[son[now][1]]=maxz[son[now][1]]=sum[son[now][1]]; } else { if(son[now][0]) ll[son[now][0]]=rr[son[now][0]]=0,maxz[son[now][0]]=val[now]; if(son[now][1]) ll[son[now][1]]=rr[son[now][1]]=0,maxz[son[now][1]]=val[now]; } return;// } if (rev[now]) { rev[now]^=1; rev[son[now][0]]^=1; rev[son[now][1]]^=1; swap(ll[son[now][0]],rr[son[now][0]]); swap(ll[son[now][1]],rr[son[now][1]]); swap(son[son[now][0]][0],son[son[now][0]][1]); swap(son[son[now][1]][0],son[son[now][1]][1]); } } void rotate(int x,int &k) { int y=fa[x],z=fa[y],l,r; l=(son[y][1]==x); r=l^1; if(y==k) k=x; else son[z][son[z][1]==y]=x; fa[son[x][r]]=y; fa[y]=x;fa[x]=z; son[y][l]=son[x][r]; son[x][r]=y; update(y); update(x); } void splay(int x,int &k) { while(x!=k) { //printf("%d %d ",x,k); int y=fa[x],z=fa[y]; if(y!=k) { if(son[y][0]==x^son[z][0]==y)rotate(x,k); else rotate(y,k); } rotate(x,k); } } int findkth(int x,int rk) { pushdown(x); int l=son[x][0],r=son[x][1]; if(size[l]+1==rk) return x; if(size[l]>=rk) return findkth(l,rk); return findkth(r,rk-size[l]-1); } void trash(int now) { if (!now) return; trash(son[now][0]),trash(son[now][1]); trashpool.push(now); fa[now]=son[now][0]=son[now][1]=tag[now]=rev[now]=0; } int split(int pos,int tot) { int x=findkth(root,pos),y=findkth(root,pos+tot+1); splay(x,root);splay(y,son[x][1]); return son[y][0]; } void asksum(int pos,int tot) {printf("%d ",sum[split(pos,tot)]);} void change(int pos,int tot,int va) { int x=split(pos,tot),y=fa[x]; val[x]=va; tag[x]=1; sum[x]=size[x]*va; if(va>=0) ll[x]=rr[x]=maxz[x]=sum[x]; else ll[x]=rr[x]=0,maxz[x]=va; update(y); update(fa[y]); } void cover(int pos,int tot) { int x=split(pos,tot),y=fa[x]; if(!tag[x]) { rev[x]^=1; swap(son[x][0],son[x][1]);swap(ll[x],rr[x]); update(y); update(fa[y]); } } void remove(int pos,int tot) { int x=split(pos,tot),y=fa[x]; trash(x); son[y][0]=0; update(y); update(fa[y]); } void build(int l,int r,int father) { if(l>r) return; int mid=(l+r)>>1,now=id[mid],last=id[father]; if(l==r) { sum[now]=key[l]; size[now]=1; tag[now]=rev[now]=0; if(key[l]>=0) ll[now]=rr[now]=maxz[now]=key[l]; else ll[now]=rr[now]=0,maxz[now]=key[l]; // return; } else build(l,mid-1,mid),build(mid+1,r,mid); val[now]=key[mid]; fa[now]=last; update(now); son[last][mid>=father]=now; } void insert(int pos,int tot) { for (int i=1; i<=tot; i++) key[i]=read(); for (int i=1; i<=tot; i++) if (!trashpool.empty()) id[i]=trashpool.front(),trashpool.pop(); else id[i]=++cnt; build(1,tot,0); int mid=(1+tot)>>1; int x=findkth(root,pos+1),y=findkth(root,pos+2),z=id[mid]; splay(x,root);splay(y,son[x][1]); fa[z]=y; son[y][0]=z; update(y); update(x); } #define sb -100000000 int main() { n=read();m=read(); maxz[0]=key[1]=key[n+2]=sb; for (int i=1; i<=n; i++) key[i+1]=read(); for (int i=1; i<=n+2; i++) id[i]=i; root=(n+3)>>1; cnt=n+2; build(1,n+2,0); char opt[10]; while (m--) { scanf("%s",opt);int pos,tot,va; switch (opt[2]) { case 'S': pos=read(),tot=read();insert(pos,tot); break; case 'L': pos=read(),tot=read();remove(pos,tot); break; case 'K': pos=read(),tot=read(),va=read(); change(pos,tot,va); break; case 'V': pos=read(),tot=read();cover(pos,tot); break; case 'T': pos=read(),tot=read();asksum(pos,tot); break; case 'X': printf("%d ",maxz[root]); break; } //for (int i=1; i<=n+1; i++) printf("%d ",val[i]);puts(""); //puts("---------------------------------------------------------------------"); } return 0; }
真的是模板题，传说中NOI最难数据结构题？？逗我？也就写了好几个小时罢了QAQ
一开始电脑爆炸，每次处理标记，n都会变化..自己瞎搞1h30min后，问char哥，char哥说，你的xx数组爆了，因为内存空间是连续的，所以波及了n...
然后30min后，电脑爆炸，于是强行考程序换YveH自带的笔记本，于是发现2h处理了电脑的智障问题....
然后发现很多问题...
such as：Splay死循啊，pushdown蛋疼啊，垃圾回收废物利用编号出毛病啊.....
以后有学弟找我要Splay模板题，不说啥了，就这道！！！