【hdu|hdu 1754 I Hate It】这是个简单题，基本上都是模板类型的：
#include
#include
#include
using namespace std;
const int maxn=50005;
int num[maxn];
struct
{
int l,r,sum;
}tree[4*maxn];
int max(int m, int n)
{
if(m>n)
return m;
return n;
}
void build (int root, int l, int r)
{
tree[root].l=l;
tree[root].r=r;
if(tree[root].l == tree[root].r)
{
tree[root].sum=num[l];
return;
}
int mid=(l+r)/2;
build(2*root, l, mid);
build(2*root+1, mid+1, r);
tree[root].sum=max(tree[2*root].sum,tree[2*root+1].sum);
}
void update(int root, int pos, int val)
{
if(tree[root].l == tree[root].r)
{
tree[root].sum=val;
return;
}
int mid=(tree[root].l + tree[root].r)/2;
if(pos <= mid)
update(2*root, pos, val);
else
update(2*root+1, pos, val);
tree[root].sum=max(tree[2*root].sum,tree[2*root+1].sum);
}
int query(int root, int L, int R)//这是核心部分
{
int s;
if(L == tree[root].l && R == tree[root].r)
return tree[root].sum;
if(R <= tree[2*root].r)
s=query(2*root, L, R);
else if(L >= tree[2*root+1].l)
s=query(2*root+1, L, R);
else
s=max(query(2*root, L, tree[2*root].r),query(2*root+1, tree[2*root+1].l, R));
return s;
}
char str[20];
int main()
{
int t, m, n, cas=1, a, b;
while(~scanf("%d%d",&m,&n))
{
for(int i=1;
i<=m;
i++)
scanf("%d",&num[i]);
build(1, 1, maxn);
for(int i=1;
i<=n;
i++)
{
scanf("%s%d%d",str,&a,&b);
if(str[0]=='Q')
printf("%d\n",query(1, a, b));
if(str[0]=='U')
update(1,a,b);
}
}
return 0;
}
