做了hdu 1166以后，感觉这个题好简单，只不过那个是区间求和，这个是区间求最值而已。。。
#include#include #include using namespace std; const int maxn = 200005; struct line { int l; int r; int max_score; }tree[4*maxn]; int n,m; int score[maxn]; void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; if(l == r) { tree[v].max_score = score[r]; return; } int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); tree[v].max_score = max(tree[v*2].max_score,tree[v*2+1].max_score); } int query(int v, int l, int r) { if(tree[v].l == l && tree[v].r == r) { return tree[v].max_score; } int mid = (tree[v].l + tree[v].r)>>1; if(r <= mid) return query(v*2,l,r); else if(l > mid) return query(v*2+1,l,r); else return max(query(v*2,l,mid),query(v*2+1,mid+1,r)); } void update(int v, int posi, int vali) { if(tree[v].l == tree[v].r) { tree[v].max_score = vali; return; } int mid = (tree[v].l+tree[v].r)>>1; if(posi <= mid) update(v*2,posi,vali); else update(v*2+1,posi,vali); tree[v].max_score = max(tree[v*2].max_score,tree[v*2+1].max_score); } int main() { while(~scanf(%d %d,&n,&m)) { for(int i = 1; i <= n; i++) scanf(%d,&score[i]); build(1,1,n); char ch[2]; int l,r,ans; int pos,val; for(int i = 1; i <= m; i++) { scanf(%s,ch); if(ch[0] == 'Q') { scanf(%d %d,&l,&r); ans = query(1,l,r); printf(%d ,ans); } else { scanf(%d %d,&pos,&val); update(1,pos,val); } } } return 0; }