思路：线段树基操 我被数组疯狂卡T，所以，要开大4倍的题目数组。。。
#include<stdio.h> #include<iostream> #include<map> #include<algorithm> #include<cstring> #include<string.h> #include<string> #include<math.h> #include<vector> #include<map> using namespace std; typedef long long ll; #define MAXN 100005*8 #define INF 0x3f3f3f3f//将近int类型最大数的一半，而且乘2不会爆int #define MOD 1000000007 int tree[MAXN]; void build(int l, int r, int node) { if (l == r) { scanf("%d", &tree[node]); return; } int mid = (l + r)>>1; build(l, mid, node<<1); build(mid+1, r, node<<1|1); tree[node] = max(tree[node<<1], tree[node<<1|1]); } void update(int p, int add, int l, int r, int node) { if (l == r) { tree[node] = add; //根结点+add return; } int m = (l + r) >> 1; if (p <= m) update(p, add, l, m, node << 1); else update(p, add, m+1, r, node << 1 | 1); tree[node] = max(tree[node << 1], tree[node << 1 | 1]); } int query(int L, int R, int l, int r, int node) { if (L <= l && r <= R) return tree[node]; int m = (l + r) >> 1, ret=0; if (L <= m) ret = max(ret, query(L, R, l, m, node << 1)); if (R > m) ret = max(ret, query(L, R, m+1, r, node << 1 | 1)); return ret; } int main() { int n, m; while(~scanf("%d%d", &n, &m)){ build(1, n, 1); for (int i = 0; i < m; ++i) { char ch[2]; int a, b; scanf("%s%d %d", ch, &a, &b); if (ch[0] == 'U') update(a, b, 1, n, 1); else printf("%d\n", query(a, b, 1, n, 1)); // getchar(); } } return 0; }