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

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

 

 

题解：

splay或fhq treap裸题，就操作多恶心人

ps：MAX-SUM所所代表的区间不能为空……

code：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 char ch; 9 bool ok; 10 void read(int &x){ 11 for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1; 12 for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar()); 13 if (ok) x=-x; 14 } 15 const int maxn=500005; 16 const int inf=500000001; 17 char s[10]; 18 int n,m,v[maxn],x,y,z; 19 typedef pair
            
              PII; 20 int random(int lim){ return rand()%lim+1;} 21 struct treap{ 22 int root,tot,stack[maxn],top,son[maxn][2],val[maxn]; 23 int siz[maxn],rev[maxn],cov[maxn],sum[maxn],res[maxn][3]; 24 void init(){res[0][2]=-inf;} 25 void reverse(int x){ if (x) swap(son[x][0],son[x][1]),swap(res[x][0],res[x][1]),rev[x]^=1;} 26 void cover(int x,int v){ if (x) cov[x]=val[x]=v,sum[x]=siz[x]*v,res[x][0]=res[x][1]=max(sum[x],0),res[x][2]=sum[x];} 27 void pushdown(int x){ 28 if (rev[x]) reverse(son[x][0]),reverse(son[x][1]),rev[x]=0; 29 if (cov[x]!=inf) cover(son[x][0],cov[x]),cover(son[x][1],cov[x]),cov[x]=inf; 30 } 31 void update(int x){ 32 int ls=son[x][0],rs=son[x][1]; 33 siz[x]=siz[ls]+siz[rs]+1; 34 sum[x]=sum[ls]+sum[rs]+val[x]; 35 res[x][0]=max(0,max(res[ls][0],sum[ls]+val[x]+res[rs][0])); 36 res[x][1]=max(0,max(res[rs][1],sum[rs]+val[x]+res[ls][1])); 37 res[x][2]=max(res[ls][1]+val[x]+res[rs][0],max(res[ls][2],res[rs][2])); 38 } 39 PII split(int x,int k){ 40 if (!k) return make_pair(0,x); 41 if (siz[x]==k) return make_pair(x,0); 42 PII tmp; pushdown(x); 43 if (k<=siz[son[x][0]]){ 44 tmp=split(son[x][0],k),son[x][0]=tmp.second,update(x); 45 return make_pair(tmp.first,x); 46 } 47 else{ 48 tmp=split(son[x][1],k-siz[son[x][0]]-1),son[x][1]=tmp.first,update(x); 49 return make_pair(x,tmp.second); 50 } 51 } 52 int merge(int x,int y){ 53 if (!x||!y) return x+y; 54 pushdown(x),pushdown(y); 55 if (random(siz[x]+siz[y])<=siz[x]){ 56 son[x][1]=merge(son[x][1],y),update(x); 57 return x; 58 } 59 else{ 60 son[y][0]=merge(x,son[y][0]),update(y); 61 return y; 62 } 63 } 64 int newnode(int v){ 65 int x=top?stack[top--]:++tot; 66 val[x]=sum[x]=v,siz[x]=1,son[x][0]=son[x][1]=rev[x]=0,res[x][0]=res[x][1]=max(v,0),res[x][2]=v,cov[x]=inf; 67 return x; 68 } 69 int build(int *v,int l,int r){ 70 if (l>r) return 0; 71 int m=(l+r)>>1,x=newnode(v[m]); 72 son[x][0]=build(v,l,m-1),son[x][1]=build(v,m+1,r),update(x); 73 return x; 74 } 75 void insert(int x,int *v,int n){ 76 PII t=split(root,x); 77 int a=t.first,b=build(v,1,n),c=t.second; 78 root=merge(a,merge(b,c)); 79 } 80 void erase(int x){ 81 stack[++top]=x; 82 if (son[x][0]) erase(son[x][0]); 83 if (son[x][1]) erase(son[x][1]); 84 } 85 void get(int l,int r,int &a,int &b,int &c){ 86 PII t=split(root,r); 87 c=t.second,t=split(t.first,l-1),a=t.first,b=t.second; 88 } 89 void erase(int l,int r){ 90 int a,b,c; get(l,r,a,b,c); 91 erase(b),root=merge(a,c); 92 } 93 void cover(int l,int r,int v){ 94 int a,b,c; get(l,r,a,b,c); 95 cover(b,v),root=merge(a,merge(b,c)); 96 } 97 void reverse(int l,int r){ 98 int a,b,c; get(l,r,a,b,c); 99 reverse(b),root=merge(a,merge(b,c));100 }101 int query_sum(int l,int r){102 int a,b,c; get(l,r,a,b,c);103 int ans=sum[b]; root=merge(a,merge(b,c));104 return ans;105 }106 int query_max(){ return res[root][2];}107 }T;108 int main(){109 srand(19990617);110 read(n),read(m),T.init();111 for (int i=1;i<=n;i++) read(v[i]);112 T.insert(0,v,n);113 while (m--){114 scanf("%s",s);115 if (s[2]=='S'){116 read(x),read(y);117 for (int i=1;i<=y;i++) read(v[i]);118 T.insert(x,v,y);119 }120 else if (s[2]=='L') read(x),read(y),T.erase(x,x+y-1);121 else if (s[2]=='K') read(x),read(y),read(z),T.cover(x,x+y-1,z);122 else if (s[2]=='V') read(x),read(y),T.reverse(x,x+y-1);123 else if (s[2]=='T') read(x),read(y),printf("%d\n",T.query_sum(x,x+y-1));124 else printf("%d\n",T.query_max());125 }126 return 0;127 }