[BZOJ1500][NOI2005]维修数列(splay)

1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 16266 Solved: 5410
[Submit][Status][Discuss]
Description

请写一个程序，要求维护一个数列，支持以下 6 种操作：

请注意，格式栏中的下划线‘ _ ’表示实际输入文件中的空格

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

Source
[Submit][Status][Discuss]

战胜恐惧去写就行了，没什么难的，不过是板子题。

主要问题就是如果模板不是非常熟练的话，几乎不可能在写代码之前将所有问题都考虑清楚，这就需要gdb和输出调试的能力，一个datamaker和一个网上的标程对拍还是比较有效的。有几个需要注意的问题：

1. cov标记只存0和1，不要存具体应该下放的数。因为MAKE-SAME的数可能为0，而v[x]本身存的就是需要下放的数。

2. 垃圾要回收，用栈就可以了，这题不卡时间和空间，可以放心的写。

3. 这题MAX-SUM要求至少包含一个数（也就是这个区间全为负数的时候不能输出0），mx[]存的是至少包含一个数的最大区间和，mxl[]和mxr[]存的是靠左/右的连续一段的最大和（可以为0）。这样就需要mx[0]=-inf

4. 多push()和upd()，其余细节考虑清楚就可以了

写了一个小时，调了三个小时。

BZOJ 150T 留念

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<iostream>
  4 #define rep(i,l,r) for (int i=l; i<=r; i++)
  5 using namespace std;
  6 
  7 const int N=1000100,inf=1000000000;
  8 int n,m,pos,tot,rt,top,k,nd,f[N],sz[N],v[N],sm[N],mxl[N],mxr[N],mx[N],ch[N][2],stk[N],C[N],R[N],a[N];
  9 char op[20];
 10 
 11 int get(){ int x; if (top) return x=stk[top--]; return ++nd; }
 12 void thr(int x){ f[x]=v[x]=sm[x]=mxl[x]=mxr[x]=mx[x]=ch[x][0]=ch[x][1]=0; stk[++top]=x; }
 13 
 14 void cov(int x,int k){
 15     sm[x]=sz[x]*k; v[x]=k;
 16     mxl[x]=mxr[x]=(k>0)?sm[x]:0; mx[x]=(k>0)?sm[x]:k;
 17     C[x]=1;
 18 }
 19 
 20 void rev(int x){ swap(ch[x][0],ch[x][1]); swap(mxl[x],mxr[x]); R[x]^=1; }
 21 
 22 void push(int x){
 23     if (C[x]){
 24         if (ch[x][0]) cov(ch[x][0],v[x]);
 25         if (ch[x][1]) cov(ch[x][1],v[x]); C[x]=0;
 26     }
 27     if (R[x]){
 28         if (ch[x][0]) rev(ch[x][0]);
 29         if (ch[x][1]) rev(ch[x][1]); R[x]=0;
 30     }
 31 }
 32 
 33 void upd(int x){
 34     int ls=ch[x][0],rs=ch[x][1];
 35     sz[x]=sz[ls]+sz[rs]+1; sm[x]=sm[ls]+sm[rs]+v[x];
 36     mx[x]=max(max(mx[ls],mx[rs]),mxr[ls]+mxl[rs]+v[x]);
 37     mxl[x]=max(mxl[ls],sm[ls]+mxl[rs]+v[x]);
 38     mxr[x]=max(mxr[rs],sm[rs]+mxr[ls]+v[x]);
 39 }
 40 
 41 int build(int l,int r){
 42     int mid=(l+r)>>1;
 43     int x=get(); v[x]=sm[x]=mx[x]=a[mid];
 44     mxl[x]=mxr[x]=(a[mid]>0)?a[mid]:0;
 45     if (l<mid) f[ch[x][0]=build(l,mid-1)]=x;
 46     if (mid<r) f[ch[x][1]=build(mid+1,r)]=x;
 47     upd(x); return x;
 48 }
 49 
 50 void rot(int &rt,int x){
 51     int y=f[x],z=f[y],w=ch[y][1]==x;
 52     if (y==rt) rt=x; else ch[z][ch[z][1]==y]=x;
 53     f[x]=z; f[y]=x; f[ch[x][w^1]]=y;
 54     ch[y][w]=ch[x][w^1]; ch[x][w^1]=y; upd(y);
 55 }
 56 
 57 void splay(int &rt,int x){
 58     while (x!=rt){
 59         int y=f[x],z=f[y];
 60         if (y!=rt){ if ((ch[z][0]==y)^(ch[y][0]==x)) rot(rt,x); else rot(rt,y); }
 61         rot(rt,x);
 62     }
 63     upd(x);
 64 }
 65 
 66 int find(int x,int k){
 67     push(x);
 68     if (sz[ch[x][0]]+1==k) return x;
 69     if (k<=sz[ch[x][0]]) return find(ch[x][0],k);
 70         else return find(ch[x][1],k-sz[ch[x][0]]-1);
 71 }
 72 
 73 void ins(int pos,int p){
 74     int x=find(rt,pos),y=find(rt,pos+1);
 75     splay(rt,x); splay(ch[rt][1],y);
 76     ch[y][0]=p; f[p]=y; upd(y); upd(x);
 77 }
 78 
 79 void era(int x){
 80     push(x);
 81     if (ch[x][0]) era(ch[x][0]);
 82     if (ch[x][1]) era(ch[x][1]);
 83     thr(x);
 84 }
 85 
 86 int split(int x,int y){
 87     x=find(rt,x); y=find(rt,y); splay(rt,x); splay(ch[x][1],y);
 88     push(ch[y][0]); return ch[y][0];
 89 }
 90 
 91 void del(int x,int y){
 92     x=find(rt,x); y=find(rt,y); splay(rt,x); splay(ch[x][1],y);
 93     era(ch[y][0]); ch[y][0]=0; upd(y); upd(x);
 94 }
 95 
 96 int main(){
 97     freopen("bzoj1500.in","r",stdin);
 98     freopen("bzoj1500.out","w",stdout);
 99     scanf("%d%d",&n,&m); mx[0]=-inf;
100     rep(i,2,n+1) scanf("%d",&a[i]); a[1]=-inf; a[n+2]=inf;
101     rt=build(1,n+2);
102     while (m--){
103         scanf("%s",op);
104         if (op[0]=='I'){
105             scanf("%d%d",&pos,&tot); rep(i,1,tot) scanf("%d",&a[i]);
106             int x=build(1,tot); ins(pos+1,x);
107         }
108         if (op[0]=='D') scanf("%d%d",&pos,&tot),del(pos,pos+tot+1);
109         if (op[0]=='M' && op[2]=='K') scanf("%d%d%d",&pos,&tot,&k),cov(split(pos,pos+tot+1),k);
110         if (op[0]=='R') scanf("%d%d",&pos,&tot),rev(split(pos,pos+tot+1));
111         if (op[0]=='G') scanf("%d%d",&pos,&tot),printf("%d
",sm[split(pos,pos+tot+1)]);
112         if (op[0]=='M' && op[2]=='X') printf("%d
",mx[split(1,sz[rt])]);
113     }
114     return 0;
115 }