|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1754
  /**//*
 題意：
給定一個長度為N(N <= 200000)的數列Si，緊接著Q(1 <= Q <= 5000)條詢問
或者修改，詢問是詢問區間的最大值，修改是修改某一個位置的值。
解法：
線段樹 或者 RMQ
思路：
最裸的線段樹區間最值，維護一顆完全二叉樹，每個結點保存兩個值，表示該結
點管理的區間的最大值和最小值，比如1號為根結點，管理區間[1, n]，每個結點p有
左兒子2*p和右兒子2*p+1，當區間兩端點相同時為葉子結點，如果p管理的是[a,b]那
么2*p則管理區間[a, (a+b)/2]，2*p+1管理區間[(a+b)/2+1, b]，如此一來就可以通
過遞歸，將兒子的信息傳遞給父親，直至根節點。
 */
#include <iostream>
using namespace std;
#define inf -(1<<30)
#define maxn 200010
struct Tree  {
int Max;
int son[2];
int l, r;
  void clear() {
son[0] = son[1] = -1;
Max = inf;
 }
void UpdateBy(Tree* ls, Tree* rs);
}T[ maxn*4 ];
int root, tot;
int val[maxn];
int GetID(int& root) {
if(root == -1) {
root = tot++;
T[root].clear();
}
return root;
}
int mmax(int a, int b) {
return a > b ? a : b;
}
void Tree::UpdateBy(Tree* ls, Tree* rs){
Max = mmax(ls->Max, rs->Max);
}
void Build(int& root, int l, int r) {
GetID(root);
T[root].l = l; T[root].r = r;
if(l == r) {
T[root].Max = val[l];
return ;
}
int mid = (l + r) >> 1;
Build(T[root].son[0], l, mid);
Build(T[root].son[1], mid+1, r);
T[root].UpdateBy(&T[T[root].son[0]], &T[T[root].son[1]]);
}
void Insert(int root, int pos, int val) {
if(pos > T[root].r || pos < T[root].l)
return ;
if(pos <= T[root].l && T[root].r <= pos) {
if(val > T[root].Max)
T[root].Max = val;
return ;
}
Insert(T[root].son[0], pos, val);
Insert(T[root].son[1], pos, val);
T[root].UpdateBy(&T[T[root].son[0]], &T[T[root].son[1]]);
}
int Query(int root, int l, int r) {
if(l > T[root].r || r < T[root].l)
return inf;
if(l <= T[root].l && T[root].r <= r) {
return T[root].Max;
}
return mmax(Query(T[root].son[0], l, r), Query(T[root].son[1], l, r));
}
int n, m;
int main() {
int i;
while(scanf("%d %d", &n, &m) != EOF) {
for(i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
root = -1;
tot = 0;
Build(root, 1, n);
while(m--) {
char str[10];
int A, B;
scanf("%s %d %d", str, &A, &B);
if(!strcmp(str, "U")) {
Insert(root, A, B);
}else {
printf("%d\n", Query(root, A, B));
}
}
}
return 0;
}
|