HDU1754.I Hate It
直接模板就可以了
代码:
//B
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const double eps=1e-;
const int maxn=*1e5+;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[maxn<<],MAX[maxn<<]; void PushUp(int rt){
//sum[rt]=sum[rt<<1]+sum[rt<<1|1];
MAX[rt]=max(MAX[rt<<],MAX[rt<<|]);
} void build(int l,int r,int rt){
if(l==r){
//scanf("%d",&sum[rt]);
scanf("%d",&MAX[rt]);
return ;
}
int m=(l+r)>>;
build(lson);
build(rson);
PushUp(rt);
}
/*
//单点增减
void update(int p,int add,int l,int r,int rt){
if(l==r){
sum[rt]+=add;
return ;
}
int m=(l+r)>>1;
if(p<=m)update(p,add,lson);
else update(p,add,rson);
PushUp(rt);
}
*/ //单点更新
void update(int p,int sc,int l,int r,int rt){
if(l==r){
MAX[rt]=sc;
return ;
}
int m=(l+r)>>;
if(p<=m)update(p,sc,lson);
else update(p,sc,rson);
PushUp(rt);
}
/*
//区间求和
int query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return sum[rt];
}
int m=(l+r)>>1;
int ret=0;
if(L<=m)ret+=query(L,R,lson);
if(R>m) ret+=query(L,R,rson);
return ret;
}
*/ //区间最值
int query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return MAX[rt];
}
int m=(l+r)>>;
int ret=;
if(L<=m)ret=max(ret,query(L,R,lson));
if(R>m) ret=max(ret,query(L,R,rson));
return ret;
} int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
build(,n,);
char s[];int a,b;
while(m--){
scanf("%s%d%d",s,&a,&b);
if(s[]=='Q')printf("%d\n",query(a,b,,n,));
else update(a,b,,n,);
}
}
return ;
}