1500: [NOI2005]维修数列

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 16266  Solved: 5410

[][][]

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

[][][]

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

主要问题就是如果模板不是非常熟练的话，几乎不可能在写代码之前将所有问题都考虑清楚，这就需要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
     
        2 #include
      
         3 #include
       
          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