平衡树并不是之前没写过，觉得有必要把平衡树变成考场上能敲的东西，也就是说，考一道诸如“维修数列”这样的送分题，要能拿满分。
维修数列。给定一个数列支持以下操作：
输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。
以上都是复制的。
这一次呢肯定比上一次敲的快了那么一点，但没有达到要求，总时间大概3h，还需很大的提升。
调试时间。。inf
主要的调试时间在边界的处理上。
1、某个子树大小。本来子树大小如果不影响答案计算的话是可以直接把边界加进来的，但是这里有求和和区间赋值，因此有必要知道区间除了边界外的真实大小。
这一次的处理方式是：假设边界点是不存在的，即size=0.这样引发的一系列调整如下：
首先，up时size的更新要注意不要加上边界点：
a[x].size=a[p].size+a[q].size+(x!=lbod && x!=rbod);
其次，find时对边界点单独处理下：
if (K>a[root].size) ans=rbod; else if (K==0) ans=lbod;
在find时，找第K个数，如果往右走要这么写：
K-=a[x].size-a[a[x].son[1]].size,x=a[x].son[1];
而不要写K-=a[a[x].son[0]].size+1，这样相当于默认x的size是1，而x有可能是边界点。
2、连边必up，访子必down。up和down在一些细节会忘了打。最典型的是splay：splay(x,top)表示把x旋到top下，如果top不为0的话应up(top)；再如find以及其他类似操作时心存侥幸以为不用down，但实际上这题有区间翻转操作，左右儿子会变，因此必须down。
3、读入。注意'-'号。
4、答案。注意边界点既要做到能传递区间答案，本身又不能对答案产生影响。这里解决的方法是在up的时候进行如下判断：
if (x!=lbod && x!=rbod) a[x].Maxsum=max(a[p].Maxsum,max(a[q].Maxsum,a[p].rsum+a[x].v+a[q].lsum)); else if (x==lbod) a[x].Maxsum=q?a[q].Maxsum:-0x3f3f3f3f; else a[x].Maxsum=p?a[p].Maxsum:-0x3f3f3f3f;
以及在区间赋值时进行如下操作：
if (x==lbod || x==rbod) a[x].v=0; if (a[x].size==0) a[x].lsum=a[x].rsum=a[x].Maxsum=-0x3f3f3f3f;
调试时果断选择区间输出。但静态查错还是不能少。
总的来说，有待提高。
1 #include<string.h> 2 #include<stdlib.h> 3 #include<stdio.h> 4 //#include<assert.h> 5 #include<algorithm> 6 //#include<iostream> 7 using namespace std; 8 9 int n,m; 10 #define maxn 500011 11 int num[maxn]; 12 13 struct Splay 14 { 15 struct Node 16 { 17 int son[2],fa; 18 bool rev,hbe; int be; 19 int v,size,sum,Maxsum,lsum,rsum; 20 }a[maxn]; 21 int root,sta[maxn],top,lbod,rbod; 22 Splay() 23 { 24 top=500000; 25 for (int i=1;i<=top;i++) sta[i]=i; 26 root=lbod=500001; rbod=500002; 27 a[0].Maxsum=-0x3f3f3f3f; 28 a[lbod].Maxsum=a[rbod].Maxsum=a[lbod].lsum=a[lbod].rsum=a[rbod].lsum=a[rbod].rsum=-0x3f3f3f3f; 29 a[lbod].v=a[lbod].size=a[lbod].sum=a[lbod].rev=a[lbod].hbe=0; 30 a[rbod].v=a[rbod].size=a[rbod].sum=a[rbod].rev=a[rbod].hbe=0; 31 a[lbod].son[1]=rbod; a[rbod].fa=lbod; 32 } 33 void up(int x) 34 { 35 if (!x) return; 36 int &p=a[x].son[0],&q=a[x].son[1]; 37 a[x].sum=a[p].sum+a[q].sum+a[x].v; 38 a[x].size=a[p].size+a[q].size+(x!=lbod && x!=rbod); 39 if (x!=lbod && x!=rbod) a[x].Maxsum=max(a[p].Maxsum,max(a[q].Maxsum,a[p].rsum+a[x].v+a[q].lsum)); 40 else if (x==lbod) a[x].Maxsum=q?a[q].Maxsum:-0x3f3f3f3f; 41 else a[x].Maxsum=p?a[p].Maxsum:-0x3f3f3f3f; 42 a[x].lsum=max(a[p].lsum,a[p].sum+a[x].v+a[q].lsum); 43 a[x].rsum=max(a[q].rsum,a[q].sum+a[x].v+a[p].rsum); 44 } 45 void besingle(int x,int v) 46 { 47 if (!x) return; 48 a[x].v=a[x].be=v; a[x].hbe=1; 49 if (x==lbod || x==rbod) a[x].v=0; 50 a[x].sum=a[x].size*v; 51 if (v>=0) a[x].lsum=a[x].rsum=a[x].Maxsum=a[x].sum; 52 else a[x].lsum=a[x].rsum=0,a[x].Maxsum=v; 53 if (a[x].size==0) a[x].lsum=a[x].rsum=a[x].Maxsum=-0x3f3f3f3f; 54 } 55 void revsingle(int x) 56 { 57 if (!x) return; 58 a[x].rev^=1; int t=a[x].son[0]; a[x].son[0]=a[x].son[1]; a[x].son[1]=t; 59 t=a[x].lsum; a[x].lsum=a[x].rsum; a[x].rsum=t; 60 } 61 void down(int x) 62 { 63 int &p=a[x].son[0],&q=a[x].son[1]; 64 if (a[x].hbe) {besingle(p,a[x].be); besingle(q,a[x].be); a[x].hbe=0;} 65 if (a[x].rev) {revsingle(p); revsingle(q); a[x].rev=0;} 66 } 67 int dsta[maxn],dtop; 68 void download(int x) 69 { 70 dtop=0; 71 for (int i=x;i;i=a[i].fa) dsta[++dtop]=i; 72 while (dtop) down(dsta[dtop--]); 73 } 74 void rotate(int x) 75 { 76 const int y=a[x].fa,z=a[y].fa; 77 bool w=(x==a[y].son[0]); 78 a[x].fa=z; 79 if (z) a[z].son[y==a[z].son[1]]=x; 80 a[y].son[w^1]=a[x].son[w]; 81 if (a[x].son[w]) a[a[x].son[w]].fa=y; 82 a[x].son[w]=y; 83 a[y].fa=x; 84 up(y); up(z); 85 } 86 void splay(int x,int top) 87 { 88 if (!x) return; 89 download(x); 90 while (a[x].fa!=top) 91 { 92 const int y=a[x].fa,z=a[y].fa; 93 if (z!=top) 94 { 95 if ((x==a[y].son[0])^(y==a[z].son[0])) rotate(x); 96 else rotate(y); 97 } 98 rotate(x); 99 } 100 up(x); 101 if (!top) root=x; else up(top); 102 } 103 int find(int K) 104 { 105 // cout<<K<<endl; 106 int x=root,ans=0; 107 if (K>a[root].size) ans=rbod; 108 else if (K==0) ans=lbod; 109 else while (x) 110 { 111 // cout<<x<<' '<<K<<endl; 112 down(x); 113 if (x==lbod) x=a[x].son[1]; 114 else if (x==rbod) x=a[x].son[0]; 115 else if (a[a[x].son[0]].size<K-1) K-=a[x].size-a[a[x].son[1]].size,x=a[x].son[1]; 116 else ans=x,x=a[x].son[0]; 117 } 118 if (ans) splay(ans,0); 119 return ans; 120 } 121 void New(int &x) {x=sta[top--];} 122 void build(int &x,int L,int R) 123 { 124 if (L>R) {x=0; return;} 125 New(x); 126 // cout<<x<<' '<<L<<' '<<R<<endl; 127 const int mid=(L+R)>>1; 128 a[x].v=a[x].sum=a[x].Maxsum=num[mid]; a[x].size=1; a[x].hbe=a[x].rev=0; 129 if (num[mid]>=0) a[x].lsum=a[x].rsum=num[mid]; 130 else a[x].lsum=a[x].rsum=0; 131 build(a[x].son[0],L,mid-1); 132 if (a[x].son[0]) a[a[x].son[0]].fa=x; 133 build(a[x].son[1],mid+1,R); 134 if (a[x].son[1]) a[a[x].son[1]].fa=x; 135 up(x); 136 } 137 void build(int &x,int n) {build(x,1,n);} 138 void insert(int pos,int tot) 139 { 140 int x=find(pos),y=a[x].son[1]; 141 // cout<<x<<' '<<y<<endl; 142 while (a[y].son[0]) down(y),y=a[y].son[0]; 143 splay(y,x); 144 build(a[y].son[0],tot); 145 a[a[y].son[0]].fa=y; 146 up(y); up(x); 147 } 148 void recycle(int x) 149 { 150 sta[++top]=x; 151 if (a[x].son[0]) recycle(a[x].son[0]); 152 if (a[x].son[1]) recycle(a[x].son[1]); 153 } 154 void Delete(int pos,int tot) 155 { 156 int y=find(pos+tot); 157 // test(); 158 int x=find(pos-1); 159 // test(); 160 splay(y,x); 161 if (a[y].son[0]) recycle(a[y].son[0]); 162 a[y].son[0]=0; up(y); up(x); 163 } 164 void Be(int pos,int tot,int v) 165 { 166 int y=find(pos+tot),x=find(pos-1); 167 splay(y,x); 168 besingle(a[y].son[0],v); 169 up(y); up(x); 170 } 171 void Rev(int pos,int tot) 172 { 173 int y=find(pos+tot),x=find(pos-1); 174 splay(y,x); 175 revsingle(a[y].son[0]); 176 up(y); up(x); 177 } 178 int Sum(int pos,int tot) 179 { 180 // cout<<pos<<' '<<tot<<endl; 181 int y=find(pos+tot); 182 // test(); 183 int x=find(pos-1); 184 // test(); 185 splay(y,x); 186 return a[a[y].son[0]].sum; 187 } 188 int Maxsum() {return a[root].Maxsum;} 189 // void test(int x) 190 // { 191 // if (!x) return; 192 //// down(x); 193 // test(a[x].son[0]); 194 // cout<<x<<' '<<a[x].v<<" size"<<a[x].size<<" sum"<<a[x].sum<<" Maxsum"<<a[x].Maxsum 195 // <<" lsum"<<a[x].lsum<<" rsum"<<a[x].rsum<<" son0 "<<a[x].son[0]<<" son1 "<<a[x].son[1] 196 // <<" be"<<a[x].be<<" rev"<<a[x].rev<<endl; 197 // test(a[x].son[1]); 198 // } 199 // void test() {test(root);cout<<endl;} 200 }t; 201 202 int qread() 203 { 204 char c;int s=0,t=1; while ((c=getchar())<'0' || c>'9') (c=='-' && (t=-1)); 205 do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s*t; 206 } 207 int main() 208 { 209 n=qread(); m=qread(); 210 for (int i=1;i<=n;i++) num[i]=qread(); 211 t.insert(0,n); 212 // t.test(); 213 char c; 214 for (int i=1,x,y,z;i<=m;i++) 215 { 216 // cout<<i<<"!!!"<<t.a[t.root].size<<' '<<t.a[0].size<<endl; 217 while ((c=getchar())<'A' || c>'Z'); 218 if (c=='I') 219 { 220 while (((c=getchar())>='A' && c<='Z') || c=='-'); 221 x=qread(); y=qread(); 222 for (int j=1;j<=y;j++) num[j]=qread(); 223 t.insert(x,y); 224 } 225 else if (c=='D') 226 { 227 while (((c=getchar())>='A' && c<='Z') || c=='-'); 228 x=qread(); y=qread(); 229 t.Delete(x,y); 230 } 231 else if (c=='R') 232 { 233 while (((c=getchar())>='A' && c<='Z') || c=='-'); 234 x=qread(); y=qread(); 235 t.Rev(x,y); 236 } 237 else if (c=='G') 238 { 239 while (((c=getchar())>='A' && c<='Z') || c=='-'); 240 x=qread(); y=qread(); 241 printf("%d ",t.Sum(x,y)); 242 } 243 else 244 { 245 c=getchar(); c=getchar(); 246 if (c=='K') 247 { 248 while (((c=getchar())>='A' && c<='Z') || c=='-'); 249 x=qread(); y=qread(); z=qread(); 250 t.Be(x,y,z); 251 } 252 else 253 { 254 while (((c=getchar())>='A' && c<='Z') || c=='-'); 255 printf("%d ",t.Maxsum()); 256 } 257 } 258 // t.up(t.lbod); 259 // t.test(); 260 } 261 return 0; 262 }