基础线段树
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 200010 #define lson p<<1 #define rson p<<1|1 struct NOD { int l,r; int best; } node[maxn<<4]; void build(int l,int r,int p) { node[p].l = l,node[p].r = r; if(l == r) { scanf("%d",&node[p].best); return; } int mid = (l+r) >> 1; build(l,mid,lson); build(mid+1,r,rson); node[p].best = max(node[lson].best,node[rson].best); } int ask(int l,int r,int p) { if(node[p].l == l && node[p].r == r) { return node[p].best; } int mid = (node[p].l+node[p].r)>>1; if(r <= mid) return ask(l,r,lson); else if(l >= mid+1) return ask(l,r,rson); else return max(ask(l,mid,lson),ask(mid+1,r,rson)); } void updata(int id,int num,int p) { if(node[p].l==node[p].r && node[p].l == id) { node[p].best = num; return; } int mid = (node[p].l+node[p].r) >> 1; if(id <= mid) updata(id,num,lson); else if(id > mid) updata(id,num,rson); node[p].best = max(node[lson].best,node[rson].best); } int main() { int n,m; while(EOF!=scanf("%d%d",&n,&m)) { build(1,n,1); while(m--) { char op[2]; scanf("%s",op); if(op[0] == 'Q') { int l,r; scanf("%d%d",&l,&r); printf("%d ",ask(l,r,1)); } else { int id,num; scanf("%d%d",&id,&num); updata(id,num,1); } } } return 0; }