裸的线段树求区间的最大值。
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 5 #define MAXN 262144 6 7 int _v[MAXN << 1]; 8 int *v = &_v[-1]; 9 10 #define lsp p<<1 11 #define rsp lsp | 1 12 #define pushup(p) (v[p] = max(v[lsp],v[rsp])) 13 #define lso l,m,lsp 14 #define rso m+1,r,rsp 15 16 #define recusive_def int l, int r, int p 17 18 void build(recusive_def) 19 { 20 if (l == r) scanf("%d", &v[p]); 21 else { 22 int m = l+r >> 1; 23 build(lso), build(rso); 24 pushup(p); 25 } 26 } 27 28 void update(int o, int oval, recusive_def) 29 { 30 if (l == r) v[p] = oval; 31 else { 32 int m = l+r >> 1; 33 if (o <= m) update(o, oval, lso); 34 else update(o, oval, rso); 35 pushup(p); 36 } 37 } 38 39 int query(int L, int R, recusive_def) 40 { 41 if (L<=l && r<=R) return v[p]; 42 else { 43 int m = l+r >> 1; 44 return max(L <= m? query(L, R, lso) : 0, R > m ? query(L, R, rso): 0); 45 } 46 } 47 48 int main(void) 49 { 50 // freopen("hdu1754.txt", "r", stdin); 51 int N, Q; 52 while(scanf("%d%d", &N, &Q) > 0){ 53 build(1, N, 1); 54 55 for(; Q; --Q) { 56 char op; 57 int L, R; 58 scanf(" %c%d%d", &op, &L, &R); 59 if (op == 'Q') printf("%d ", query(L,R, 1, N, 1)); 60 else update(L, R, 1, N, 1); 61 } 62 } 63 return 0; 64 }
| 2014-06-03 21:21:37 | Accepted | 1754 | 1109MS | 2348K | 1149 B | G++ |
