因为shift操作中的数不多，所以直接用单点更新模拟一下就好了。
太久不写线段树，手好生啊，不是这错一下就是那错一下。
PS：输入写的我有点蛋疼，不知道谁有没有更好的写法。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int maxn = 100000 + 10; 9 const int maxnode = (maxn << 2); 10 const int INF = 0x3f3f3f3f; 11 12 void scan(int& x) 13 { 14 x = 0; 15 char c = ' '; 16 while(c < '0' || c > '9') c = getchar(); 17 while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } 18 } 19 20 int qL, qR; 21 int p, v; 22 int n, Q; 23 int minv[maxnode]; 24 25 int a[maxn]; 26 27 void build(int o, int L, int R) 28 { 29 if(L == R) { scan(a[L]); minv[o] = a[L]; return ; } 30 int M = (L + R) / 2; 31 build(o<<1, L, M); 32 build(o<<1|1, M+1, R); 33 minv[o] = min(minv[o<<1], minv[o<<1|1]); 34 } 35 36 void update(int o, int L, int R) 37 { 38 //if(v >= minv[o]) return ; 39 if(L == R) { minv[o] = v; return ; } 40 41 int M = (L + R) / 2; 42 if(p <= M) update(o<<1, L, M); 43 else update(o<<1|1, M+1, R); 44 minv[o] = min(minv[o<<1], minv[o<<1|1]); 45 } 46 47 int query(int o, int L, int R) 48 { 49 if(qL <= L && R <= qR) return minv[o]; 50 int ans = INF; 51 int M = (L + R) / 2; 52 if(qL <= M) ans = min(ans, query(o<<1, L, M)); 53 if(qR > M) ans = min(ans, query(o<<1|1, M+1, R)); 54 return ans; 55 } 56 57 char op[50]; 58 59 int main() 60 { 61 while(scanf("%d%d", &n, &Q) == 2 && n) 62 { 63 build(1, 1, n); 64 while(Q--) 65 { 66 scanf("%s", op); 67 int l = strlen(op); 68 if(op[0] == 'q') 69 { 70 int i = 6; 71 qL = 0; 72 while(i < l && op[i] >= '0' && op[i] <= '9') { qL = qL * 10 + op[i] - '0'; i++; } 73 while(i < l && (op[i] < '0' || op[i] > '9')) i++; 74 qR = 0; 75 while(i < l && op[i] >= '0' && op[i] <= '9') { qR = qR * 10 + op[i] - '0'; i++; } 76 printf("%d\n", query(1, 1, n)); 77 } 78 else 79 { 80 vector hehe; 81 82 for(int i = 6; i < l;) 83 { 84 while(i < l && (op[i] < '0' || op[i] > '9')) i++; 85 if(i >= l) break; 86 int x = 0; 87 while(i < l && op[i] >= '0' && op[i] <= '9') { x = x * 10 + op[i] - '0'; i++; } 88 hehe.push_back(x); 89 } 90 91 int sz = hehe.size(); 92 for(int i = 0; i < sz - 1; i++) 93 { 94 v = a[hehe[i + 1]]; 95 p = hehe[i]; 96 update(1, 1, n); 97 } 98 v = a[hehe[0]]; 99 p = hehe[sz - 1];100 update(1, 1, n);101 102 int t = a[hehe[0]];103 for(int i = 0; i < sz - 1; i++) a[hehe[i]] = a[hehe[i+1]];104 a[hehe[sz - 1]] = t;105 }106 }107 }108 109 return 0;110 }