思路：與我發表的上一遍求和的思想一樣 只是現在變成求最大值而已
AC代碼：
#include#include #include #include #include using namespace std; inline int Max(int a, int b) { return a > b ? a : b; } const int MAXN = 200001; // 區間范圍 struct { int l, r, m; // l 左端點，r 右端點，m 為該區間的最大分數 } tree[MAXN*4]; int a[MAXN]; void creat(int t, int l, int r) { tree[t].l = l, tree[t].r = r; if(l == r) // 葉子節點 { tree[t].m = a[l]; return; //遞歸出口 } int m = (l+r) / 2; creat(t*2, l, m), creat(t*2+1, m+1, r); // 左孩子 tree[t].m = Max(tree[t*2].m, tree[t*2+1].m); // 右孩子 } void update(int t, int n, int v) // 把n 點的值更新為v { if(tree[t].l == tree[t].r && tree[t].l == n) { tree[t].m = v; return; } if(n <= tree[t*2].r) update(t*2, n, v); else update(t*2+1, n, v); tree[t].m = Max(tree[t*2].m, tree[t*2+1].m); } int query(int t, int l, int r) // 查詢t 節點在【l，r】區間范圍的最大值 { if(l == tree[t].l && r == tree[t].r) return tree[t].m; int s; if(r <= tree[t*2].r) s = query(t*2, l, r); else if(l >= tree[t*2+1].l) s= query(t*2+1, l, r); else s = Max(query(t*2, l, tree[t*2].r), query(t*2+1, tree[t*2+1].l, r)); return s; } int main() { int n, m, i, x1, x2; char s[2]; while(scanf("%d%d", &n, &m) != EOF) { for(i = 1; i <= n; i++) scanf("%d", &a[i]); creat(1, 1, n); // 根節點標號為1，區間為【1，n】 while(m--) { scanf("%s%d%d", s, &x1, &x2); if(s[0] == 'Q') printf("%d\n", query(1, x1, x2)); // 查詢 else update(1, x1, x2); // 更新 } } return 0; }
