一看基本就是线段树的题目，考察的是区间更新 和区间查找，
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; // typedef struct { int l,r; int maxn; }Node; int n,m; int num[200000 + 5]; Node tree[200005 * 20]; int build(int root,int left,int right) { int mid; tree[root].l = left; tree[root].r = right; if(left == right) return tree[root].maxn = num[left]; mid = (left + right)/2; int x = build(2 * root,left,mid); int y = build(2 * root + 1,mid+1,right); return tree[root].maxn = max(x,y); } int find(int root,int left,int right) {//查找操作 int mid; if(tree[root].l > right || tree[root].r < left) return 0; if(left <= tree[root].l && tree[root].r <= right) return tree[root].maxn; int x = find(2 * root,left,right); int y = find(2 * root + 1,left,right); return max(x,y); } int update(int root,int pos,int val) {//区间更新 if(pos < tree[root].l || tree[root].r < pos) return tree[root].maxn; if(tree[root].l == pos && tree[root].r == pos) return tree[root].maxn = val; int x = update(2 * root,pos,val); int y = update(2 * root + 1,pos,val); tree[root].maxn = max(x,y); return tree[root].maxn; } int main() { char c; int x,y; while(scanf("%d %d",&n,&m) == 2) { for(int i=1;i<=n;i++) scanf("%d",&num[i]); build(1,1,n); for(int i=1;i<=m;i++) { getchar(); scanf("%c %d %d",&c,&x,&y); if(c == 'Q') printf("%d\n",find(1,x,y)); else { num[x] = y; update(1,x,y); } } } return EXIT_SUCCESS; }