BZOJ1500 [NOI2005]维修数列

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

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

Sample Output

-1
10
1
10

HINT

正解：splay

解题报告：

　　简单说一下操作的实现吧：

　　1、insert操作：因为有大量元素插入，如果每个都新建结点的话空间开不下，所以我们必须要回收空间，也就是说之前delete操作删掉的结点我要把它回收利用。因为我们是在pos后插入若干元素，那么我可以把pos变成根结点，pos+1变成右子树的根，那么pos+1的左子树为空，我可以先把需要插入的元素构成一棵树，再把这棵树插入到左子树上，往上update一遍。

　　2、delete操作：考虑删除若干元素该怎么做。因为我们想删除一段区间[l,r]，那么我们可以把l-1旋转到根，r+1旋转到根的右子树的根，那么此时r+1的左子树就是要删除的，我们可以直接把左子树删掉，然后回收结点。注意我需要扫一遍这需要删除的整棵左子树，把上面的标记什么的全部清空。看上去这个复杂度是O（n）的，但实际上题目中说插入元素不超过400w，也就是说删除元素也不会超过这么多，所以复杂度没有问题。

　　3、make-same操作：因为我们要把一段区间修改为一个数，所以与上述做法类似，旋转使得需要操作的区间处在一棵子树中，然后给根结点打上标记，表示这个点为根结点的子树全部修改为一个值。每次旋转的时候记得下传就可以了。

　　4、reverse操作：翻转区间与make-same类似，给结点打上标记，表示这棵子树需要翻转，每次下传即可。可以画图发现，每次我下传的时候把左右子树交换则最终可以起到翻转的效果。

　　5、get-sum操作：得到区间之后直接调用根结点的维护的sum值即可。

　　6、max-sum操作：我可以对于每个结点，存储一个它所控制的区间的前缀最大值、后缀最大值和整体最大值，做法经典，不再赘述。

　　大概总结：

　　这道题的的确确是一道码农题，但是只要思维清晰，对于splay的操作熟悉的话，打起来也会很快。

　　细节很多，写的时候一定谨慎，因为查起错来会很麻烦，务必尽最大努力一遍写对。想清楚再写，想一想模板的模式，没事的时候也可以复习复习splay模板，也想一想自己打splay的时候犯过什么错。

（　我的查错经过：（蒟蒻的查错辛酸史）

　　错误一：翻转标记下传时，不是赋值，而是把儿子结点的标记^1；

　　错误二：求第x大的元素时忘记pushdown；

　　错误三：插入的时候，我得到pos的位置时不应该直接把pos旋转，而应该先找到位置处在pos的元素是谁；

　　错误四：删除的时候，遍历整棵删除子树时需要清空所有标记，但是我忘记清空翻转和make-same标记了。）

  1 //It is made by ljh2000
  2 #include <iostream>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <algorithm>
  8 #include <ctime>
  9 #include <vector>
 10 #include <queue>
 11 #include <map>
 12 #include <set>
 13 using namespace std;
 14 typedef long long LL;
 15 const int inf = (1<<30);
 16 const int MAXN = 500011;
 17 int rt,tot,n,m;
 18 int a[MAXN],lx[MAXN],rx[MAXN],mx[MAXN];
 19 int tr[MAXN][2],same[MAXN],tag[MAXN],father[MAXN];
 20 int sum[MAXN],size[MAXN],val[MAXN],id[MAXN];
 21 char ch[12];
 22 queue<int>Q;
 23 
 24 inline int getint()
 25 {
 26     int w=0,q=0; char c=getchar();
 27     while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
 28     while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
 29 }
 30 
 31 inline void Del(int x){
 32     if(!x) return ;
 33     int l=tr[x][0],r=tr[x][1];
 34     if(l) Del(l); if(r) Del(r);
 35     father[x]=0; tr[x][0]=tr[x][1]=0; 
 36     val[x]=lx[x]=rx[x]=mx[x]=0; 
 37     same[x]=tag[x]=0;//!!!
 38     Q.push(x);
 39 }
 40 
 41 inline void update(int x){
 42     int l=tr[x][0],r=tr[x][1]; size[x]=size[l]+size[r]+1; sum[x]=sum[l]+sum[r]+val[x];
 43     mx[x]=max(max(mx[l],mx[r]),rx[l]+val[x]+lx[r]); lx[x]=max(lx[l],sum[l]+val[x]+lx[r]); rx[x]=max(rx[r],sum[r]+val[x]+rx[l]);
 44 }
 45 
 46 inline void pushdown(int x){
 47     int l=tr[x][0],r=tr[x][1];
 48     if(same[x]) {
 49     same[x]=tag[x]=0; 
 50     if(l) {
 51         same[l]=1; val[l]=val[x]; sum[l]=val[l]*size[l];
 52         if(val[x]>0) mx[l]=lx[l]=rx[l]=sum[l]; else mx[l]=val[x],lx[l]=rx[l]=0;
 53     }
 54     if(r) {
 55         same[r]=1; val[r]=val[x]; sum[r]=val[r]*size[r];
 56         if(val[x]>0) mx[r]=lx[r]=rx[r]=sum[r]; else mx[r]=val[x],lx[r]=rx[r]=0;
 57     }
 58     }
 59     if(tag[x]) {
 60     tag[x]=0; tag[l]^=1; tag[r]^=1; swap(tr[l][0],tr[l][1]);
 61     swap(tr[r][0],tr[r][1]); swap(lx[l],rx[l]); swap(lx[r],rx[r]);      
 62     }
 63 }
 64 
 65 inline void rotate(int x,int &rt){
 66     int y=father[x],z=father[y];
 67     int l=(tr[y][1]==x),r=l^1; 
 68     if(y==rt) rt=x; else tr[z][(tr[z][1]==y)]=x;
 69     father[x]=z; father[tr[x][r]]=y; tr[y][l]=tr[x][r];
 70     tr[x][r]=y; father[y]=x; 
 71     update(y); update(x);
 72 }
 73 
 74 inline void splay(int x,int &rt){
 75     while(x!=rt) {
 76     int y=father[x],z=father[y];
 77     if(y!=rt) {
 78         if((tr[z][0]==y)^(tr[y][0]==x)) rotate(x,rt);//不同边转自己!!!
 79         else rotate(y,rt);
 80     }
 81     rotate(x,rt);
 82     }
 83 }
 84 
 85 inline void build(int l,int r,int fa){
 86     if(l>r) return ;  int mid=(l+r)/2;
 87     if(l==r) {
 88     size[id[l]]=1; same[id[l]]=tag[id[l]]=0; sum[id[l]]=mx[id[l]]=a[l];
 89     if(a[l]>0) lx[id[l]]=rx[id[l]]=a[l]; else lx[id[l]]=rx[id[l]]=0;        
 90     }
 91     else build(l,mid-1,mid),build(mid+1,r,mid);
 92     tr[id[fa]][mid>fa]=id[mid]; val[id[mid]]=a[mid];
 93     father[id[mid]]=id[fa];  update(id[mid]);
 94 }
 95 
 96 inline int rank(int x,int k){
 97     pushdown(x);//!!!
 98     int l=tr[x][0],r=tr[x][1]; if(size[l]+1==k) return x;
 99     if(size[l]>=k) return rank(l,k); else return rank(r,k-size[l]-1);
100 }
101 
102 inline void split(int pos,int num){//操作区间为[pos+1,pos+num]，则需要旋转pos到根，pos+num+1到右子树
103     int x=rank(rt,pos); splay(x,rt);
104     x=rank(rt,pos+num+1); splay(x,tr[rt][1]);
105 }
106 
107 inline void insert(){
108     int pos=getint(),num=getint();
109     for(int i=1;i<=num;i++) {
110     a[i]=getint();
111     if(!Q.empty()) id[i]=Q.front(),Q.pop();
112     else id[i]=++tot;
113     }
114     int x=rank(rt,pos+1); splay(x,rt); //!!!
115     x=rank(rt,pos+2); splay(x,tr[rt][1]);
116     build(1,num,0); int now_root=id[(1+num)/2];
117     father[now_root]=tr[rt][1]; tr[tr[rt][1]][0]=now_root;
118     update(tr[rt][1]); update(rt);
119 }
120 
121 inline void del(){
122     int pos=getint(),num=getint(); split(pos,num);
123     Del(tr[tr[rt][1]][0]); tr[tr[rt][1]][0]=0;
124     update(tr[rt][1]); update(rt);
125 }
126 
127 inline void reverse(){
128     int pos=getint(),num=getint(); split(pos,num);
129     int x=tr[tr[rt][1]][0]; if(same[x]) return ;
130     tag[x]^=1;//!!!
131     swap(tr[x][0],tr[x][1]); swap(lx[x],rx[x]); 
132     update(tr[rt][1]); update(rt);
133 }
134 
135 inline void get_sum(){
136     int pos=getint(),num=getint(); split(pos,num);
137     printf("%d
",sum[tr[tr[rt][1]][0]]);
138 }
139 
140 inline void makesame(){
141     int pos=getint(),num=getint(),CC=getint(); split(pos,num);
142     int x=tr[tr[rt][1]][0]; same[x]=1; val[x]=CC; sum[x]=size[x]*CC; 
143     if(CC>0) lx[x]=rx[x]=mx[x]=sum[x]; else lx[x]=rx[x]=0,mx[x]=val[x];
144     update(tr[rt][1]); update(rt);
145 }
146 
147 inline void work(){
148     n=getint(); m=getint(); a[1]=a[n+2]=-inf; mx[0]=-inf;
149     for(int i=2;i<=n+1;i++) a[i]=getint(); tot=n+2; rt=(1+n+2)/2;
150     for(int i=1;i<=n+2;i++) id[i]=i; build(1,n+2,0);
151     while(m--) {
152     scanf("%s",ch); lx[0]=rx[0]=size[0]=father[0]=val[0]=0; mx[0]=-inf;
153     if(ch[0]=='I') insert();
154     else if(ch[0]=='D') del();
155     else if(ch[0]=='R') reverse();
156     else if(ch[0]=='G') get_sum();
157     else if(ch[2]=='K') makesame();
158     else printf("%d
",mx[rt]);
159     }
160 }
161 
162 int main()
163 {
164     work();
165     return 0;
166 }