【留坑】uva12299

这么sb的题本来想练练手记过就是过不了
拍半天也没问题
留坑
哪天有空了去linux下面试试
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<algorithm>
  5 #include<iostream>
  6 
  7 using namespace std;
  8 template<typename Q> bool read(Q& x) {
  9     static char c, f;
 10     for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1;
 11     for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0';
 12     if(f) x = -x; return c != ')';
 13 }
 14 template<typename Q> Q read() {
 15     static Q x; read(x); return x;
 16 }
 17 
 18 const int N = 100000 + 10;
 19 
 20 int a[N], n;
 21 
 22 struct SegmentTree {
 23     int da[N * 4];
 24     
 25     #define mid ((l + r) >> 1)
 26     #define ls s << 1, l, mid
 27     #define rs s << 1 | 1, mid + 1, r
 28     
 29     void build(int s, int l, int r) {
 30         if(l == r) return da[s] = a[l], void();
 31         build(ls), build(rs);
 32         da[s] = min(da[s << 1], da[s << 1 | 1]);
 33     }
 34     
 35     int lft, rgt, w;
 36     
 37     int query(int s, int l, int r) {
 38         if(lft <= l && r <= rgt) return da[s];
 39         if(rgt <= mid) return query(ls);
 40         if(mid < lft) return query(rs);
 41         return min(query(ls), query(rs));
 42     }
 43     
 44     void modify(int s, int l, int r) {
 45         if(l == lft) return da[s] = w, void();
 46         if(lft <= mid) modify(ls); else modify(rs);
 47         da[s] = min(da[s << 1], da[s << 1 | 1]);
 48     }
 49     
 50     int Q(int l, int r) {
 51         return lft = l, rgt = r, query(1, 1, n);
 52     }
 53     
 54     void M(int p, int w) {
 55         lft = p, this->w = w;
 56         modify(1, 1, n);
 57     }
 58 }seg;
 59 
 60 int b[N], tot;
 61 
 62 char enter[1000000];
 63 
 64 int main() {
 65 #ifdef DEBUG
 66     freopen("in.txt", "r", stdin);
 67     freopen("out.txt", "w", stdout);
 68 #endif
 69     
 70     int m, l, r, x;
 71     read(n), read(m);
 72     for(int i = 1; i <= n; i++) {
 73         read(a[i]);
 74     }
 75     seg.build(1, 1, n);
 76 //    gets(enter);
 77     char opt[10000];
 78     
 79     for(int i = 1; i <= m; i++) {
 80 //        fprintf(stderr, "%d
", i);
 81         scanf("%[^(]", opt);
 82         if(opt[0] == 'q') {
 83             read(l), read(r);
 84             printf("%d
", seg.Q(l, r));
 85         }else {
 86             tot = 0;
 87             while(1) {
 88                 int t = read(x);
 89                 b[tot++] = x;
 90                 if(!t) break;
 91             }
 92             if(tot == 1) continue;
 93             reverse(b, b + tot);
 94             int last = a[b[tot - 1]];
 95             for(int i = 0; i < tot; i++) {
 96                 seg.M(b[i], last);
 97                 swap(a[b[i]], last);
 98             }
 99         }
100         gets(enter);
101     }
102     
103     return 0;
104 }
View Code