HDu 1754 I Hate It(単点更新、区間最値)
1389 ワード
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define lson i<<1,l,m
#define rson i<<1|1,m+1,r
#define maxn 200005
int Max[maxn<<2];
void PushUp(int i)
{
Max[i]=max(Max[i<<1],Max[i<<1|1]);
}
void build(int i,int l,int r)
{
if(l==r) {scanf("%d",&Max[i]);getchar();return;}
int m=(l+r)>>1;
build(lson);
build(rson);
PushUp(i);
}
void update(int a,int b,int i,int l,int r)
{
if(l==r) {Max[i]=b;return;}
int m=(l+r)>>1;
if(a<=m) update(a,b,lson);
else update(a,b,rson);
PushUp(i);
}
int query(int L,int R,int i,int l,int r)
{
if(L<=l&&r<=R) return Max[i];
int m=(l+r)>>1;
int ans=0;
if(L<=m) ans=max(ans,query(L,R,lson));
if(R>m) ans=max(ans,query(L,R,rson));
return ans;
}
int main()
{
int m,n;
while(scanf("%d%d",&n,&m)!=EOF)
{
build(1,1,n);
char s;
while(m--)
{
int a,b;
scanf("%c%d%d",&s,&a,&b);
getchar();
if(s=='Q') printf("%d
",query(a,b,1,1,n));
else if(s=='U') update(a,b,1,1,n);
}
}
return 0;
}