时间限制：3 s   内存限制：64 MB

 

【问题描述】

请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）

操作编号	输入文件中的格式	说明
1.  插入	INSERT_posi_tot_c1_c2_..._ctot	在当前数列的第 posi 个数字后插入 tot 个数字：c1, c2, …, ctot；若在数列首插 入，则 posi 为 0
2.  删除	DELETE_posi_tot	从当前数列的第 posi 个数字开始连续 删除 tot 个数字
3.  修改	MAKE-SAME_posi_tot_c	将当前数列的第 posi 个数字开始的连 续 tot 个数字统一修改为 c
4.  翻转	REVERSE_posi_tot	取出从当前数列的第 posi 个数字开始 的 tot 个数字，翻转后放入原来的位置
5.  求和	GET-SUM_posi_tot	计算从当前数列开始的第 posi 个数字 开始的 tot 个数字的和并输出
6.  求和最 大的子列	MAX-SUM	求出当前数列中和最大的一段子列， 并输出最大和

【输入格式】

输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M表示要进行的操作数目。

第 2 行包含 N 个数字，描述初始时的数列。

以下 M 行，每行一条命令，格式参见问题描述中的表格。

【输出格式】

对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结果，每个答案（数字）占一行。

【输入样例】

9 82 -6 3 5 1 -5 -3 6 3GET-SUM 5 4MAX-SUM INSERT 8 3 -5 7 2DELETE 12 1MAKE-SAME 3 3 2REVERSE 3 6GET-SUM 5 4MAX-SUM

【输出样例】

-110110

【样例说明】

初始时，我们拥有数列 2 -6 3 5 1 -5 -3 6 3

执行操作 GET-SUM 5 4，表示求出数列中从第 5 个数开始连续 4 个数字之和，1+(-5)+(-3)+6 = -1：

2     -6     3      5      1     -5    -3     6      3

执行操作 MAX-SUM，表示要求求出当前数列中最大的一段和，应为 3+5+1+(-5)+(-3)+6+3 = 10：

2     -6     3      5      1     -5    -3     6      3

执行操作 INSERT 8 3 -5 7 2，即在数列中第 8 个数字后插入-5 7 2，

2     -6     3      5      1     -5    -3     6     -5     7      2      3

执行操作 DELETE 12 1，表示删除第 12 个数字，即最后一个：

2     -6     3      5      1     -5    -3     6     -5     7      2

执行操作 MAKE-SAME 3 3 2，表示从第 3 个数开始的 3 个数字，统一修改为 2：

2	-6	3	5	1	-5	-3	6	-5	7	2

改为

2	-6	2	2	2	-5	-3	6	-5	7	2

执行操作 REVERSE 3 6，表示取出数

 

 

splay终极模板题，我一共写了两遍，第一遍自己yy的巨丑，后来看了hzwer的blog改的优美了一点。

1 #include
      
         2 using namespace std;  3 const int inf=5e5+10;  4 int ch[inf][2],siz[inf],v[inf],fa[inf],sum[inf],se[inf],lazy[inf],lm[inf],ma[inf],rm[inf],a[inf];  5 int st[inf],top,n,m,rt,sz;  6 int ne(){  7     return top?st[top--]:++sz;  8 }  9 void clea(int x,int val){ 10     ch[x][0]=ch[x][1]=fa[x]=lazy[x]=0; 11     siz[x]=1; 12     se[x]=1001; 13     sum[x]=lm[x]=ma[x]=rm[x]=v[x]=val; 14 } 15 int get(int x){ 16     return ch[fa[x]][1]==x; 17 } 18 void update(int x){ 19     if(v[x]==-0x3fffffff) 20     sum[x]=sum[ch[x][0]]+sum[ch[x][1]]; 21     else sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+v[x]; 22     siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1; 23     if(!ch[x][0]&&!ch[x][1]) 24         lm[x]=rm[x]=sum[x]=ma[x]=v[x]; 25     else if(!ch[x][0]) 26         lm[x]=max(v[x],v[x]+lm[ch[x][1]]), 27         rm[x]=max(rm[ch[x][1]],sum[ch[x][1]]+v[x]), 28         ma[x]=max(ma[ch[x][1]],max(lm[ch[x][1]]+v[x],v[x])); 29     else if(!ch[x][1]) 30         lm[x]=max(lm[ch[x][0]],sum[ch[x][0]]+v[x]), 31         rm[x]=max(v[x],rm[ch[x][0]]+v[x]), 32         ma[x]=max(ma[ch[x][0]],max(rm[ch[x][0]]+v[x],v[x])); 33     else  34         ma[x]=max(max(ma[ch[x][0]],ma[ch[x][1]]),max(rm[ch[x][0]]+v[x]+lm[ch[x][1]],max(0,max(rm[ch[x][0]],lm[ch[x][1]]))+v[x])), 35         lm[x]=max(lm[ch[x][0]],max(sum[ch[x][0]]+v[x],sum[ch[x][0]]+v[x]+lm[ch[x][1]])), 36         rm[x]=max(rm[ch[x][1]],max(sum[ch[x][1]]+v[x],sum[ch[x][1]]+v[x]+rm[ch[x][0]])); 37 } 38 void pushdown(int x){ 39     if(se[x]!=1001){ 40         v[x]=se[x]; 41         if(ch[x][0]){ 42             se[ch[x][0]]=se[x]; 43             sum[ch[x][0]]=se[x]*siz[ch[x][0]]; 44             if(se[x]<0)lm[ch[x][0]]=rm[ch[x][0]]=ma[ch[x][0]]=se[x]; 45             else lm[ch[x][0]]=rm[ch[x][0]]=ma[ch[x][0]]=sum[ch[x][0]];     46         } 47         if(ch[x][1]){ 48             se[ch[x][1]]=se[x]; 49             sum[ch[x][1]]=se[x]*siz[ch[x][1]]; 50             if(se[x]<0)lm[ch[x][1]]=rm[ch[x][1]]=ma[ch[x][1]]=se[x]; 51             else lm[ch[x][1]]=rm[ch[x][1]]=ma[ch[x][1]]=sum[ch[x][1]];     52         } 53         se[x]=1001; 54         lazy[x]=0; 55     } 56     if(lazy[x]){ 57         lazy[x]=0; 58         swap(ch[x][0],ch[x][1]); 59         lazy[ch[x][0]]^=1; 60         swap(lm[ch[x][0]],rm[ch[x][0]]); 61         lazy[ch[x][1]]^=1; 62         swap(lm[ch[x][1]],rm[ch[x][1]]); 63     } 64 } 65 void zig(int x){ 66     int old=fa[x],oldf=fa[old]; 67     pushdown(old); 68     pushdown(x); 69     int p=get(x); 70     if(oldf)ch[oldf][get(old)]=x; 71     fa[x]=oldf; 72     fa[ch[old][p]=ch[x][p^1]]=old; 73     fa[ch[x][p^1]=old]=x; 74     update(old); 75     update(x); 76 } 77 void splay(int x,int aim=0){ 78     for(int f;(f=fa[x])!=aim;zig(x)) 79         if(fa[f]!=aim)zig(get(x)==get(f)?f:x); 80     if(!aim)rt=x; 81 } 82 int kth(int x,int ned){ 83     pushdown(x); 84     if(siz[ch[x][0]]+1==ned)return x; 85     if(ned
       
        r)return 0; 90     int mid=(l+r)>>1; 91     int x=ne(); 92     if(!rt)rt=x; 93     clea(x,a[mid]); 94     if(flag){ 95         if(mid==1||mid==n){ 96             ma[x]=lm[x]=rm[x]=v[x]=-0x3fffffff; 97         } 98     } 99     fa[x]=f;100     int ls=build(l,mid-1,x,flag);101     int rs=build(mid+1,r,x,flag);102     if(ls)ch[x][0]=ls;103     if(rs)ch[x][1]=rs;104     update(x);105     return x;106 }107 void del(int x){108     st[++top]=x;109     if(ch[x][0])del(ch[x][0]);110     if(ch[x][1])del(ch[x][1]);111 }112 void out(int x){113     pushdown(x);114     if(ch[x][0])out(ch[x][0]);115     printf("%d ",v[x]);116 //    printf("%d %d %d %d %d\n",x,v[x],siz[x],sum[x],ma[x]);117     if(ch[x][1])out(ch[x][1]);118 }119 int main()120 {121 //    freopen("1.txt","r",stdin);122 //    freopen("b.out","w",stdout);123     scanf("%d%d",&n,&m);124     n+=2;125     for(int i=2;i
       
      

update写的巨大，无数行的特判。

 

然后我看了hzwer的写法，一开始还质疑他update的正确性，后来仔细思考之后发现他是正确的。

1 #include
      
         2 using namespace std;  3 const int inf=5e5+10;  4 int ch[inf][2],fa[inf],v[inf],siz[inf];  5 int sum[inf],lm[inf],rm[inf],ma[inf],lazy[inf],se[inf];  6 int st[inf],top,n,m,rt,sz,a[inf];  7 int ne(){  8     return top?st[top--]:++sz;  9 } 10 int clear(int x,int val){ 11     fa[x]=ch[x][0]=ch[x][1]=0; 12     siz[x]=1;se[x]=1001;lazy[x]=0; 13     sum[x]=v[x]=ma[x]=val; 14     if(val<0)lm[x]=rm[x]=0; 15     else lm[x]=rm[x]=val; 16 } 17 int get(int x){ 18     return ch[fa[x]][1]==x; 19 } 20 void update(int x){ 21     int ls=ch[x][0],rs=ch[x][1]; 22     sum[x]=sum[ls]+sum[rs]+v[x]; 23     siz[x]=siz[ls]+siz[rs]+1; 24     ma[x]=max(max(ma[ls],ma[rs]),rm[ls]+v[x]+lm[rs]); 25     lm[x]=max(lm[ls],sum[ls]+v[x]+lm[rs]); 26     rm[x]=max(rm[rs],sum[rs]+v[x]+rm[ls]); 27 } 28 void pushdown(int x){ 29     int ls=ch[x][0],rs=ch[x][1]; 30     if(se[x]!=1001){ 31         v[x]=se[x]; 32         lazy[x]=0; 33         se[x]=1001; 34         se[ls]=se[rs]=v[x]; 35         sum[ls]=siz[ls]*v[x]; 36         sum[rs]=siz[rs]*v[x]; 37         if(v[x]>0) 38         lm[ls]=rm[ls]=ma[ls]=sum[ls], 39         lm[rs]=rm[rs]=ma[rs]=sum[rs]; 40         else  41         lm[ls]=rm[ls]=lm[rs]=rm[rs]=0, 42         ma[ls]=ma[rs]=v[x]; 43     } 44     if(lazy[x]){ 45         lazy[ls]^=1;lazy[rs]^=1; 46         swap(ch[ls][0],ch[ls][1]); 47         swap(ch[rs][0],ch[rs][1]); 48         swap(lm[ls],rm[ls]); 49         swap(lm[rs],rm[rs]); 50         lazy[x]=0; 51     } 52 } 53 void zig(int x){ 54     int old=fa[x],oldf=fa[old]; 55     pushdown(old); 56     pushdown(x); 57     int p=get(x); 58     if(oldf)ch[oldf][get(old)]=x; 59     fa[x]=oldf; 60     fa[ch[old][p]=ch[x][p^1]]=old; 61     fa[ch[x][p^1]=old]=x; 62     update(old); 63     update(x); 64 } 65 void splay(int x,int aim=0){ 66     for(int f;(f=fa[x])!=aim;zig(x)) 67         if(fa[f]!=aim)zig(get(x)==get(f)?f:x); 68     if(!aim)rt=x; 69 } 70 int build(int l,int r,int f){ 71     if(l>r)return 0; 72     int mid=(l+r)>>1; 73     int x=ne(); 74     clear(x,a[mid]); 75     fa[x]=f; 76     if(!rt)rt=x; 77     int ls=build(l,mid-1,x); 78     int rs=build(mid+1,r,x); 79     if(ls)ch[x][0]=ls; 80     if(rs)ch[x][1]=rs; 81     update(x); 82     return x; 83 } 84 int kth(int x,int ned){ 85     pushdown(x); 86     int ls=ch[x][0],rs=ch[x][1]; 87     if(siz[ls]+1==ned)return x; 88     if(ned
       
        0)lm[o]=rm[o]=ma[o]=sum[o];137                 else lm[o]=rm[o]=0,ma[o]=z;138             }139             else if(s[0]=='R')lazy[o]^=1,swap(lm[o],rm[o]),swap(ch[o][0],ch[o][1]);140             else if(s[0]=='G')printf("%d\n",sum[o]);141             update(r),update(l);142         }143     }144 //    out(rt);145     return 0;146 }
       
      

 

至于第二种写法update正确性

如果这样写，哨兵直接赋值-inf，那么会使得最左边那条链和最右边那条链sum维护，以及左边的lm和右边的rm维护错误，但是，最左边一条链的lm，他们对我要求的结果是不会造成任何影响的，只会使得他们那一条链上的lm维护错误，仅此而已。rm同理。而对于sum，因为我们具有splay操作，查询区间是不可能包含哨兵节点的，也就是我要查询的那个区间的子树的sum是不会受哨兵节点的值影响的，他依然是正确的。