1 #include <set>  2 #include <map>  3 #include <cmath>  4 #include <ctime>  5 #include <queue>  6 #include <stack>  7 #include <cstdio>  8 #include <string>  9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 typedef unsigned long long ull; 16 typedef long long ll; 17 const int inf = 0x3f3f3f3f; 18 const double eps = 1e-8; 19 const int maxn = 1e5+100; 20 int siz[maxn],minv[maxn],rev[maxn],addv[maxn],key[maxn]; 21 int ch[maxn][2],a[maxn],pre[maxn],s[maxn]; 22 int n,tot1,tot2,root; 23 void NewNode(int &r,int father,int k) 24 { 25     if (tot2) 26         r = s[tot2--]; 27     else 28         r = ++tot1; 29     pre[r] = father; 30     key[r] = k; 31     siz[r] = 1; 32     minv[r] = k; 33     ch[r][0] = ch[r][1] = 0; 34 } 35 void update_Rev(int r) 36 { 37     if (!r) 38         return ; 39     swap(ch[r][0],ch[r][1]); 40     rev[r] ^= 1; 41 } 42 void push_up(int r) 43 { 44     siz[r] = siz[ch[r][0]] + siz[ch[r][1]] + 1; 45     minv[r] = min(key[r],min(minv[ch[r][0]],minv[ch[r][1]])); 46 } 47 void update_add(int r,int val) 48 { 49     if (!r) 50         return ; 51     key[r] += val; 52     addv[r] += val; 53     minv[r] += val; 54 } 55 void push_down(int r) 56 { 57     if (rev[r]) 58     { 59         update_Rev(ch[r][0]); 60         update_Rev(ch[r][1]); 61         rev[r] = 0; 62     } 63     if (addv[r]) 64     { 65         update_add(ch[r][0],addv[r]); 66         update_add(ch[r][1],addv[r]); 67         addv[r] = 0; 68     } 69 } 70  71 void build(int &x,int l,int r,int father) 72 { 73     if (l > r) 74         return; 75     int mid = (l + r) >> 1; 76     NewNode(x,father,a[mid]); 77     build(ch[x][0],l,mid-1,x); 78     build(ch[x][1],mid+1,r,x); 79     push_up(x); 80 } 81 void init() 82 { 83     tot1 = root = tot2 = 0; 84     for (int i = 1; i <= n; i++) 85         scanf ("%d",a+i); 86     minv[root] = inf; 87     NewNode(root,0,-1); 88     NewNode(ch[root][1],root,-1); 89     build(ch[ch[root][1]][0],1,n,ch[root][1]); 90     push_up(root); 91     push_up(ch[root][1]); 92 } 93 void Rotate(int x,int kind) 94 { 95     int y = pre[x]; 96     push_down(y); 97     push_down(x); 98     ch[y][!kind] = ch[x][kind]; 99     pre[ch[x][kind]] = y;100     if (pre[y])101         ch[pre[y]][ch[pre[y]][1] == y] = x;102     pre[x] = pre[y];103     ch[x][kind] = y;104     pre[y] = x;105     push_up(y);106 }107 void Splay(int r,int goal)108 {109     push_down(r);110     while (pre[r] != goal)111     {112         if (pre[pre[r]] == goal)113         {114             push_down(pre[r]);115             push_down(r);116             Rotate(r,ch[pre[r]][0] == r);117         }118         else119         {120             int y = pre[r];121             push_down(pre[y]);122             push_down(y);123             push_down(r);124             int kind = (ch[pre[y]][1] == y);125             if (ch[y][kind] == r)126             {127                 Rotate(y,!kind);128                 Rotate(r,!kind);129             }130             else131             {132                 Rotate(r,kind);133                 Rotate(r,!kind);134             }135         }136     }137     push_up(r);138     if (goal == 0)139         root = r;140 }141 int Get_kth(int r,int k)142 {143     push_down(r);144     int t = siz[ch[r][0]] + 1;145     if (t == k)146         return r;147     else if (t <= k)148         return Get_kth(ch[r][1],k-t);149     else150         return Get_kth(ch[r][0],k);151 }152 void eraser(int r)153 {154     if (!r)155         return;156     s[++tot2] = r;157     eraser(ch[r][0]);158     eraser(ch[r][1]);159 }160 void Delete(int x)161 {162     Splay(Get_kth(root,x),0);163     Splay(Get_kth(root,x+2),root);164     eraser(ch[ch[root][1]][0]);165     pre[ch[ch[root][1]][0]] = 0;166     ch[ch[root][1]][0] = 0;167     push_up(ch[root][1]);168     push_up(root);169 }170 void Insert(int x,int val)171 {172     Splay(Get_kth(root,x+1),0);173     Splay(Get_kth(root,x+2),root);174     NewNode(ch[ch[root][1]][0],ch[root][1],val);175     push_up(ch[root][1]);176     push_up(root);177 }178 void ADD(int u,int v,int val)179 {180     Splay(Get_kth(root,u),0);181     Splay(Get_kth(root,v+2),root);182     update_add(ch[ch[root][1]][0],val);183     push_up(ch[root][1]);184     push_up(root);185 }186 int query(int ua,int ub)187 {188     Splay(Get_kth(root,ua),0);189     Splay(Get_kth(root,ub+2),root);190     return minv[ch[ch[root][1]][0]];191 }192 void Reverse (int u,int v)193 {194     Splay (Get_kth(root,u),0);195     Splay (Get_kth(root,v+2),root);196     update_Rev (ch[ch[root][1]][0]);197     push_up (ch[root][1]);198     push_up (root);199 }200 void revolve(int u,int v,int c)201 {202     int len = (v - u + 1);203     c  %= len;204     if (!c)205         return;206     Reverse(u,v);207     Reverse(u,u+c-1);208     Reverse(u+c,v);209 }210 int main(void)211 {212     #ifndef ONLINE_JUDGE213         freopen("in.txt","r",stdin);214     #endif215     while (~scanf ("%d",&n))216     {217         init();218         int m;219         scanf ("%d",&m);220         for (int i = 0; i < m; i++)221         {222             char op[10];223             int u,v,c;224             scanf ("%s",op);225             if (strcmp(op,"ADD") == 0)226             {227                 scanf ("%d%d%d",&u,&v,&c);228                 ADD(u,v,c);229             }230             if (strcmp(op,"REVERSE") == 0)231             {232                 scanf ("%d%d",&u,&v);233                 Reverse(u,v);234             }235             if (strcmp(op,"REVOLVE") == 0)236             {237                 scanf ("%d%d%d",&u,&v,&c);238                 revolve(u,v,c);239             }240             if (strcmp(op,"INSERT") == 0)241             {242                 scanf ("%d%d",&u,&v);243                 Insert(u,v);244             }245             if (strcmp(op,"DELETE") == 0)246             {247                 scanf ("%d",&u);248                 Delete(u);249             }250             if (strcmp(op,"MIN") == 0)251             {252                 scanf ("%d%d",&u,&v);253                 printf("%d\n",query(u,v));254             }255         }256     }257     return 0;258 }