1 //poj3580  2 //#pragma comment(linker,"/STACK:102400000,102400000")  3 #include <cstdio>  4 #include <set>  5 #include <map>  6 #include <ctime>  7 #include <cctype>  8 #include <string>  9 #include <cstring> 10 #include <cstdlib> 11 #include <cmath> 12 #include <assert.h> 13 #include <algorithm> 14 #include <iostream> 15 #include <climits> 16 #include <queue> 17 #include <vector> 18  19 #define dte(x) cout << #x << " = " << x << endl; 20 #define scaf2(x,y) scaf(x);scaf(y); 21 #define mkp make_pair 22    23 using namespace std; 24 template<typename T>inline void scaf(T&v) 25 { 26     char ch = getchar(); 27     for(; ch < ‘0‘ || ch > ‘9‘; ch = getchar()); 28     for(v = 0; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) v = (v << 1) +(v << 3) + ch - ‘0‘; 29 } 30 typedef long long LL; 31 typedef unsigned long long ULL; 32 typedef pair <int, int> PII; 33 const int maxN = 2e5 + 10; 34 const LL mod = 1e9 + 7; 35 const double eps = 1e-9; 36 const LL oo = ~ 0U >> 2; 37  38 int inn[maxN]; 39  40 struct SplayTree 41 { 42     static const int smaxN = 4e5 + 10; 43     #define keyNode chird[chird[root][1]][0] 44     int item[smaxN]; 45     int parent[smaxN]; 46     int sz[smaxN]; 47     int chird[smaxN][2]; 48      49     int root, vtot; 50      51     SplayTree() 52     { 53         root = vtot = 0; 54         item[0] = -1; 55         parent[0] = sz[0] = chird[0][0] = chird[0][1] = 0; 56     } 57      58     void Rotate(const int& x, const int& lr) 59     {//lr - > 0: leftRotate 1: rightRotate 60         int y = parent[x]; 61         pushDown(y); pushDown(x); 62         chird[y][! lr] = chird[x][lr]; 63         if (chird[x][lr]) parent[chird[x][lr]] = y; 64         parent[x] = parent[y]; 65         if (parent[y]) 66         { 67             if (chird[parent[y]][0] == y) chird[parent[y]][0] = x; 68             else chird[parent[y]][1] = x; 69         } 70         chird[x][lr] = y; parent[y] = x; 71         pushUp(y); 72     } 73      74     void Splay(int x, const int& target) 75     {//Splay x to target‘t chird -- target must be x‘s ancestor 76         for (pushDown(x); parent[x] != target;) 77         { 78             if (parent[parent[x]] == target)/*x‘s father‘s father is target -> rotate x to x‘s father*/ 79             { 80                 if (chird[parent[x]][0] == x) Rotate(x, 1); 81                 else Rotate(x, 0); 82             }else 83             { 84                 int y = parent[x], z = parent[parent[x]]; 85                 if (chird[z][0] == y)/*y is z‘s lson*/ 86                 { 87                     if (chird[y][0] == x) Rotate(y, 1), Rotate(x, 1);//yi zi xing 88                     else Rotate(x, 0), Rotate(x, 1);//zhi zi xing 89                 }else 90                 { 91                     if (chird[y][0] == x) Rotate(x, 1), Rotate(x, 0);//zhi 92                     else Rotate(y, 0), Rotate(x, 0);//yi 93                 } 94             } 95         } 96         pushUp(x); 97         if (!target) root = x; 98     } 99     100     int Search(const int& target)101     {102         int x = root;103         while (x)104         {105             if (item[x] == target) break;106             if (item[x] > target) x = chird[x][0];107             else x = chird[x][1];108         }109         if (x) Splay(x, 0);110         return x;111     }112     113     void Insert(const int& target, const int& _id)114     {115 //        if (Search(target)) return;//exist?116         int x = root, y = 0, lr;117         while (x)118         {119             y = x; ++ sz[y];120             if (item[x] > target) x = chird[x][0];121             else x = chird[x][1];122         }123         if (item[y] > target) lr = 0;124         else lr = 1;125         sz[x = ++ vtot] = 1;126         parent[x] = y; chird[y][lr] = x;127         item[x] = target;128         chird[x][0] = chird[x][1] = 0;129         Splay(x, 0);130     }131     132     void Delete(const int& target)133     {134         int x = Search(target);135         if (!x) return;//no exist136         int lc = chird[x][0], rc = chird[x][1];137         sz[x] = parent[lc] = parent[rc] = chird[x][0] = chird[x][1] = 0;138         if (!lc) root = rc;139         else140         {141             for (pushDown(lc); chird[lc][1]; pushDown(lc)) lc = chird[lc][1];142             Splay(lc, 0);143             parent[rc] = lc;144             chird[lc][1] = rc;145             pushUp(root);146         }147     }148     149     int findParent(const int& target)150     {151         int x = root, ret = 0;152         while (x)153         {154             if (target <= item[x]) x = chird[x][0];155             else ret = x, x = chird[x][1];156         }157         if (ret) Splay(ret, 0);158         return ret;159     }160     161     int findSuccessor(const int& target)162     {163         int x = root, ret = 0;164         while (x)165         {166             if (target >= item[x]) x = chird[x][1];167             else ret = x, x = chird[x][0];168         }169         if (ret) Splay(ret, 0);170         return ret;171     }172     173     int findKth(int k, const int& target)174     {175         int x = root;176         while (x)177         {178             pushDown(x);179              int y = sz[chird[x][0]];180             if (y == k) break;181             if (y > k) x = chird[x][0];182             else x = chird[x][1], k -= y + 1;183         }184         if (x) Splay(x, target);185         return x;//item[x]???186     }187     188     void Treaval(const int& x, int& num)189     {190         if (x)191         {192             pushDown(x);193             Treaval(chird[x][0], num);194             printf("%d", item[x]);195             if (-- num) putchar(32);196             else putchar(10);197             Treaval(chird[x][1], num);198         }199     }200     201     void outPut(int n)202     {203         int m = n;204         findKth(0, 0);205         Treaval(root, m);206     }207     208     void newNode(int& x, const int& val, const int& father)209     {210         item[x = ++ vtot] = val; sz[x] = 1; parent[x] = father; 211         minVal[x] = val; rev[x] = false; addLazy[x] = 0;212         chird[x][0] = chird[x][1] = 0;213     }214     215     void buildSplay(int n)216     {217         root = vtot = 0;218         item[0] = 0; rev[0] = 0; addLazy[0] = 0; minVal[0] = oo;219         parent[0] = sz[0] = chird[0][0] = chird[0][1] = 0;220         newNode(root, oo, 0);//ex node?221         newNode(chird[root][1], oo, root);222         buildTree(keyNode, 1, n, chird[root][1]);223         pushUp(chird[root][1]);224         pushUp(root);225     }226     227     void buildTree(int& x, const int& l, const int& r, const int& father)228     {229         if (l > r) return;230         int mid = l + r >> 1;231         newNode(x, inn[mid], father);232         buildTree(chird[x][0], l, mid - 1, x);233         buildTree(chird[x][1], mid + 1, r, x);234         pushUp(x);235     }236     237     void pushUp(const int& x)238     {239         sz[x] = sz[chird[x][0]] + sz[chird[x][1]] + 1;240         minVal[x] = item[x];241         if (chird[x][0]) minVal[x] = min(minVal[x], minVal[chird[x][0]]);242         if (chird[x][1]) minVal[x] = min(minVal[x], minVal[chird[x][1]]);;243     }244     245     void pushDown(const int& x)246     {247         if (rev[x])248         {249             int lc = chird[x][0], rc = chird[x][1];250             swap(chird[x][0], chird[x][1]);251             if (lc) rev[lc] ^= 1;252             if (rc) rev[rc] ^= 1;253             rev[x] ^= 1;254         }255         if (addLazy[x])256         {257             if (chird[x][0])258             {259                 item[chird[x][0]] += addLazy[x];260                 minVal[chird[x][0]] += addLazy[x];261                 addLazy[chird[x][0]] += addLazy[x];262             }263             if (chird[x][1])264             {265                 item[chird[x][1]] += addLazy[x];266                 minVal[chird[x][1]] += addLazy[x];267                 addLazy[chird[x][1]] += addLazy[x];268             }269             addLazy[x] = 0;270         }271     }272     273     void add(const int& l, const int& r, const int& v)274     {275         findKth(l - 1, 0); findKth(r + 1, root);276         item[keyNode] += v;277         addLazy[keyNode] += v;278         minVal[keyNode] += v;279         Splay(keyNode, 0);280     }281     282     void insVal(const int& l, const int& v)283     {284         findKth(l, 0); findKth(l + 1, root);285         if (keyNode) while (1);286         newNode(keyNode, v, chird[root][1]);287         Splay(keyNode, 0);288     }289     290     void del(const int& target)291     {292         findKth(target, 0);293         pushDown(root);294         int x = root;295         int lc = chird[x][0], rc = chird[x][1];296         sz[x] = parent[lc] = parent[rc] = chird[x][0] = chird[x][1] = 0;297         if (!lc) root = rc;298         else299         {300             for (pushDown(lc); chird[lc][1]; pushDown(lc)) lc = chird[lc][1];301             Splay(lc, 0);302             parent[rc] = lc;303             chird[lc][1] = rc;304             pushUp(root);305         }306     }307     308     int getMin(const int& l, const int& r)309     {310         findKth(l - 1, 0); findKth(r + 1, root);311         return minVal[keyNode];312     }313     314     void Reverse(const int& l, const int& r)315     {316         findKth(l - 1, 0); findKth(r + 1, root);317         rev[keyNode] ^= 1;318         Splay(keyNode, 0);319     }320     321     void Revolve(const int& l, const int& r, const int& v)322     {323         int rr = r - v;324         int ll = rr + 1;325         findKth(ll - 1, 0); findKth(r + 1, root);326         int x = keyNode; keyNode = 0; parent[x] = 0;327         pushUp(chird[root][1]); pushUp(root);328         findKth(l - 1, 0); findKth(l, root);329         keyNode = x;330         parent[keyNode] = chird[root][1];331         pushUp(chird[root][1]); pushUp(root);332         Splay(keyNode, 0);333     }334     335     int minVal[smaxN];336     int addLazy[smaxN];337     bool rev[smaxN];338 }spt;339 340 int main()341 {342 //    freopen("ok.out", "w", stdout);343     int n, i, m;344     int l, r, v;345     char opt[10];346 //    scaf(n);347     scanf("%d", &n);348     for (i = 1; i <= n; ++ i)349 //        scaf(inn[i]);350         scanf("%d", &inn[i]);351     spt.buildSplay(n);352 //    scaf(m);353     scanf("%d", &m);354     while (m --)355     {356         scanf("%s", opt);357 //        printf("%s\n", opt);358         if (‘A‘ == opt[0])359         {360 //            scaf2(l, r); scaf(v);361             scanf("%d%d%d", &l, &r, &v);362             spt.add(l, r, v);363         }else if (‘I‘ == opt[0])364         {365 //            scaf2(l, v);366             scanf("%d%d", &l, &v);367             spt.insVal(l, v);368         }else if (‘D‘ == opt[0])369         {370 //            scaf(v);371             scanf("%d", &v);372              spt.del(v);373 //             spt.outPut(spt.sz[spt.root]);374         }else if (‘M‘ == opt[0])375         {376 //            scaf2(l, r);377             scanf("%d%d", &l, &r);378             printf("%d\n", spt.getMin(l, r));379         }else if (‘E‘ == opt[3])380         {381 //            scaf2(l, r);382             scanf("%d%d", &l, &r);383             spt.Reverse(l, r);384 //            spt.outPut(spt.sz[spt.root]);385         }else386         {387 //            scaf2(l, r); scaf(v);388             scanf("%d%d%d", &l, &r, &v);389             int len = r - l + 1;390             v = (v % len + len) % len;391             if (v) spt.Revolve(l, r, v);392         }393         spt.findKth(0, 0);394 //        spt.outPut(spt.sz[spt.root]);395 //        printf("%d\n", spt.sz[spt.root]);396     }397     return 0;398 }