|
|
题目链接：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;
}
|