HDOJ 1754 I Hate It 线段树：单点替换 成求段最值
//HDOJ 1754 I Hate It 线段树：单点替换 成求段最值/*题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1754题目大意：有ｎ（0<ｎ<=200000）个学生，已知每个学生的初始成绩。有ｍ（0<ｍ<5000）次操作：１、将ａ学生的成绩改为ｂ；２、查询区间[ａ,ｂ]中成绩最高的思路：线段树叶子结点记录每个学生的成绩，父亲结点记录其两个子孩子中较高的成绩，这样根节点记录的就是所有成绩中最高的。更新操作从根结点开始查找，一定在左孩子或右孩子其中一个，查询后替换，然后往上更新父结点。查询操作和敌兵布阵一样，直至记录答案的时候不是累加结果，而是去更大的值，同样递归实现，时间复杂度Ｏ(logn);*/#include <stdio.h>#define root 1#define MAXN 600000int n,m,x,y,a[MAXN];int Max(int a,int b){ return a>b?a:b;}struct node{ int left; int right; int max;}t[MAXN];int build(int p,int left,int right){ t[p].left = left; t[p].right = right; if (left == right) return t[p].max = a[left]; int m=(left+right)/2; return t[p].max = Max(build(p*2, left, m),build(p*2+1, m+1, right));}int query(int p, int left ,int right){ if (t[p].left==left && t[p].right==right) return t[p].max; int m=(t[p].left+t[p].right)/2; if (right<=m) return query(p*2,left,right); if (left>m) return query(p*2+1,left,right); return Max(query(p*2,left,m),query(p*2+1,m+1,right));}void update(int p,int x,int y){ if (t[p].left == t[p].right) t[p].max=y; else { int m = (t[p].left+t[p].right) / 2; if(x<=m){ update(p*2,x,y); t[p].max=Max(t[p].max,t[p*2].max); } else{ update(p*2+1,x,y); t[p].max=Max(t[p].max,t[p*2+1].max); } }}int main(){ int i; char c; while(scanf("%d %d",&n,&m)==2) { for(i=1;i<=n;i++) scanf("%d",&a[i]); getchar(); build(root,1,n); while(m--){ scanf("%c %d %d",&c,&x,&y); getchar(); if(c=='Q') printf("%d\n",query(root,x,y)); else update(root,x,y); } } return 0;}