5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5
5 6 5 9 HintHuge input,the C function scanf() will work better than cin
這會兒在看線段樹,做個題試試
線段樹功能:update:單點替換 query:區間最值
AC代碼:
#include#include #include using namespace std; const int maxn = 200005; int MAX[maxn<<2]; void pushup(int rt) { MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]); } void build(int l, int r, int rt) { if(l == r) { scanf("%d", &MAX[rt]); return ; } int m = (l + r) >> 1; build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); pushup(rt); } void update(int p, int sc, int l, int r, int rt) { if(l == r) { MAX[rt] = sc; return; } int m = (l + r) >> 1; if(p <= m) update(p, sc, l, m, rt << 1); else update(p, sc, m + 1, r, rt << 1 | 1); pushup(rt); } int query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { return MAX[rt]; } int m = (l + r) >> 1; int ret = 0; if(L <= m) ret = max(ret, query(L, R, l, m, rt << 1)); if(R > m) ret = max(ret, query(L, R, m + 1, r, rt << 1 | 1)); return ret; } int main() { int n, m; while(scanf("%d %d", &n, &m) != EOF) { build(1, n, 1); while(m--) { char ord[5]; int a, b; scanf("%s %d %d", ord, &a, &b); if(ord[0] == 'Q') printf("%d\n", query(a, b, 1, n, 1)); else update(a, b, 1, n, 1); } } return 0; }