1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 200010 12 #define LL long long 13 #define INF 0xfffffff 14 #define key_value ch[ch[root][1]][0] 15 const double eps = 1e-8; 16 const double pi = acos(-1.0); 17 const double inf = ~0u>>2; 18 using namespace std; 19 int a[N]; 20 struct splay_tree 21 { 22     int pre[N],size[N]; 23     int ch[N][2]; 24     int root,tot; 25     int lz2[N]; 26     LL s[N],lz1[N],key[N]; 27 //    void dfs(int x) 28 //    { 29 //        if(x) 30 //        { 31 //            dfs(ch[x][0]); 32 //            printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,key=%2d lz1 = %d lz2 = %d min = %d\n", 33 //                   x,ch[x][0],ch[x][1],pre[x],size[x],key[x],lz1[x],lz2[x],s[x]); 34 //            dfs(ch[x][1]); 35 //        } 36 //    } 37 //    void debug() 38 //    { 39 //        printf("root:%d\n",root); 40 //        dfs(root); 41 //    } 42 //以上用于debug*/ 43     void newnode(int &x,int v,int fa)//新建一结点 44     { 45         x = ++tot; 46         ch[x][0]=ch[x][1] = 0; 47         pre[x] = fa; 48         lz1[x] = lz2[x] = 0; 49         size[x] = 1; 50         s[x] = v; 51         key[x] = v; 52     } 53     void pushdown(int w) 54     { 55         int l = ch[w][0],r = ch[w][1]; 56         if(lz1[w]) 57         { 58             lz1[l] += lz1[w]; 59             lz1[r] += lz1[w]; 60             s[l]+=lz1[w]; 61             s[r]+=lz1[w]; 62             key[l]+=lz1[w]; 63             key[r]+=lz1[w]; 64             lz1[w] = 0; 65         } 66         if(lz2[w]) 67         { 68             lz2[l]^=lz2[w]; 69             lz2[r]^=lz2[w]; 70             swap(ch[w][0],ch[w][1]); 71             lz2[w] = 0; 72         } 73     } 74     void pushup(int w) 75     { 76         size[w] = size[ch[w][0]]+size[ch[w][1]]+1; 77         s[w] = key[w]; 78         if(ch[w][0]) 79             s[w] = min(s[w],s[ch[w][0]]); 80         if(ch[w][1]) 81             s[w] = min(s[w],s[ch[w][1]]); 82     } 83     void rotate(int r,int kind) 84     { 85         int y = pre[r]; 86         pushdown(y); 87         pushdown(r); 88         ch[y][!kind] = ch[r][kind]; 89         pre[ch[r][kind]] = y; 90         if(pre[y]) 91         { 92             ch[pre[y]][ch[pre[y]][1]==y] = r; 93         } 94         pre[r] = pre[y]; 95         ch[r][kind] = y; 96         pre[y] = r; 97         pushup(y); 98         pushup(r); 99     }100     void splay(int r,int goal)101     {102         pushdown(r);103         while(pre[r]!=goal)104         {105             if(pre[pre[r]]==goal)106             {107                 rotate(r,ch[pre[r]][0]==r);108             }109             else110             {111                 int y = pre[r];112                 int kind = (ch[pre[y]][0]==y);113                 if(ch[y][kind]==r)114                 {115                     rotate(r,!kind);116                     rotate(r,kind);117                 }118                 else119                 {120                     rotate(y,kind);121                     rotate(r,kind);122                 }123             }124         }125         pushup(r);126         if(goal==0) root = r;127     }128     int get_k(int k)129     {130         int r = root;131         pushdown(r);132         while(size[ch[r][0]]+1!=k)133         {134             if(size[ch[r][0]]>=k)135                 r = ch[r][0];136             else137             {138                 k-=(size[ch[r][0]]+1);139                 r = ch[r][1];140             }141             pushdown(r);142         }143         return r;144     }145     void add(int l,int r,int k)146     {147         splay(get_k(l),0);148         splay(get_k(r+2),root);149         lz1[key_value]+=k;150         s[key_value]+=k;151         key[key_value]+=k;152         pushup(ch[root][1]);153         pushup(root);154     }155     LL query(int l,int r)156     {157         splay(get_k(l),0);158         splay(get_k(r+2),root);159         return s[key_value];160     }161     void reverse(int l,int r)162     {163         splay(get_k(l),0);164         splay(get_k(r+2),root);165         lz2[key_value]^=1;166         pushup(ch[root][1]);167         pushup(root);168     }169     void revolve(int l,int r,int k)170     {171         splay(get_k(r-k+1),0);172         splay(get_k(r+2),root);173         int nod = key_value;174         key_value = http://www.mamicode.com/0;175         pushup(ch[root][1]);176         pushup(root);177 178         splay(get_k(l),0);179         splay(get_k(l+1),root);180         key_value =http://www.mamicode.com/ nod;181         pre[nod] = ch[root][1];182         pushup(ch[root][1]);183         pushup(root);184     }185     void insert(int k,int p)186     {187         splay(get_k(k),0);188         splay(get_k(k+1),root);189         newnode(key_value,p,ch[root][1]);190         pushup(ch[root][1]);191         pushup(root);192     }193     void updelete(int k)194     {195         splay(get_k(k),0);196         splay(get_k(k+2),root);197         key_value = http://www.mamicode.com/0;198         pushup(ch[root][1]);199         pushup(root);200     }201     void build(int &x,int l,int r,int fa)202     {203         int m = (l+r)>>1;204         if(l>r) return ;205         newnode(x,a[m],fa);206         build(ch[x][0],l,m-1,x);207         build(ch[x][1],m+1,r,x);208         pushup(x);209     }210     void init(int o)211     {212         int i;213         for(i = 1; i <= o ; i++)214             scanf("%d",&a[i]);215         size[0] = ch[0][0] = ch[0][1] =  key[0] = lz1[0] = lz2[0] = s[0] = 0;216         root = tot = 0;217         newnode(root,0,0);218         newnode(ch[root][1],0,root);219         build(ch[ch[root][1]][0],1,o,ch[root][1]);220         size[root] = 2;221         pushup(ch[root][1]);222         pushup(root);223     }224 //    void work()225 //    {226 //        for(int i =  1; i <= size[root] ;i++)227 //        cout<<key[get_k(i)]<<" ";228 //        puts("");229 //    }230 } SP;231 int main()232 {233     int n,q,k,x,y;234     char sq[10];235     while(scanf("%d",&n)!=EOF)236     {237         SP.init(n);238         scanf("%d",&q);239         while(q--)240         {241             scanf("%s",sq);242             if(sq[0]==‘A‘)243             {244                 scanf("%d%d%d",&x,&y,&k);245                 SP.add(x,y,k);246             }247             else if(strcmp(sq,"REVERSE")==0)248             {249                 scanf("%d%d",&x,&y);250                 SP.reverse(x,y);251             }252             else if(strcmp(sq,"REVOLVE")==0)253             {254                 scanf("%d%d%d",&x,&y,&k);255                 if(k<=0) continue;256                 k = k%(y-x+1);257                 SP.revolve(x,y,k);258             }259             else if(sq[0]==‘I‘)260             {261                 scanf("%d%d",&k,&x);262                 SP.insert(k+1,x);263             }264             else if(sq[0]==‘D‘)265             {266                 scanf("%d",&k);267                 SP.updelete(k);268             }269             else if(sq[0]==‘M‘)270             {271                 scanf("%d%d",&x,&y);272                 printf("%d\n",SP.query(x,y));273             }274             //SP.work();275         }276     }277     return 0;278 }