题目链接：HDU 1754 I Hate It 思路：对模板进行简单的修改，求区间内最大值。 AC代码讲解：
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<iomanip> #include<set> #include<stack> #include<ctime> #include<queue> #define LOCAL #define pi 3.1415926 #define e 2.718281828459 #define mst(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f; using namespace std; #define maxn 200000 int sum[maxn<<2]; int a[maxn]; void build(int l,int r,int rt){ if(l == r){ sum[rt] = a[l]; return ; } int m = (l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); sum[rt] = max(sum[rt<<1] , sum[rt<<1|1]);//修改部分，将求和改成求最值 } void update(int L,int C,int l,int r,int rt){ if(l == r){//找到叶子节点就修改 sum[rt] = C; return ; } int m = (l+r)>>1; if(L <= m) update(L,C,l,m,rt<<1); else update(L,C,m+1,r,rt<<1|1); sum[rt] = max(sum[rt<<1] , sum[rt<<1|1]);//递归跟新有关的最值 } int query(int L,int R, int l,int r,int rt){//重点 if(L <=l && r <= R) return sum[rt]; int m = (r+l)>>1; int nmax = 0; if(L <= m) nmax = max(nmax,query(L,R,l,m,rt<<1));//先设定一个最小的值，然后比较重叠部分的最值 if(R > m) nmax = max(nmax,query(L,R,m+1,r,rt<<1|1)); return nmax; } int main(){ int n ,m; while(scanf("%d%d",&n,&m) == 2){ for(int i = 1; i <= n; i++) scanf("%d",&a[i]); build(1,n,1); char c; int ans , a, b; while(m--){ getchar(); scanf("%c",&c); if(c == 'Q'){ scanf("%d%d",&a,&b); ans = query(a, b, 1, n, 1); printf("%d\n",ans); } else if(c == 'U'){ scanf("%d%d",&a,&b); update(a, b, 1, n, 1); } } } return 0; }