首页 > 代码库 > BZOJ1500 [NOI2005]维修数列
BZOJ1500 [NOI2005]维修数列
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
正解：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\n",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\n",mx[rt]); 159 } 160 } 161 162 int main() 163 { 164 work(); 165 return 0; 166 }
BZOJ1500 [NOI2005]维修数列