一看基本就是线段树的题目，考察的是区间更新 和区间查找，
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#define ll long long
#define eps 1e-7
#define inf 0xfffffff
const ll INF = 1ll<<61;
using namespace std;
//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::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;
}