HDU 1754 线段树-I Hate It

题意：

---

中文题目，不解释了。

---

题解：

---

本题使用线段树做，目标是求最大值，因为每次操作知识修改其中一项的值，所以也可以用树状数组做，我用的是线段树。

---

#include <iostream> #include <stdio.h> #include <string.h> #include <cmath> #define MAXN 200000+10 using namespace std; int Max[4*MAXN]; int ql,qr,p,v; inline void build(int r,int L, int R) { if(L == R) scanf("%d",&Max[r]); else { int M = (L+R)/2; build(r*2,L,M); build(r*2+1,M+1,R); Max[r] = max(Max[r*2],Max[r*2+1]); } } inline void update(int r, int L, int R) { int M = (L+R)/2; if(L == R) Max[r] = v; else { if(p <= M) update(r*2,L,M); else update(r*2+1,M+1,R); Max[r] = max(Max[r*2],Max[r*2+1]); } } inline int query(int r, int L, int R) { int ans = -1; int M = (L+R)/2; if(ql <= L && R <= qr) return Max[r]; if(qr <= M) return query(r*2,L,M); else if(ql > M) return query(r*2+1,M+1,R); else ans = max(query(r*2,L,M),query(r*2+1,M+1,R)); return ans; } int main() { int n,m; int a,b; char op[2]; while(~scanf("%d%d",&n,&m)) { build(1,1,n); for(int i = 1; i <= m; i++) { scanf("%s%d%d",op,&a,&b); if(op[0] == 'Q') { ql = a; qr = b; cout << query(1,1,n) << endl; } else { p = a; v = b; update(1,1,n); } } } return 0; }