HDU 1754——I Hate It(線分木の単点修正)
1770 ワード
基礎テンプレートの問題
<span style="font-size:18px;"><strong>#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define M 200001
#define ls(x) x<<1
#define rs(x) x<<1|1
#define inf 0x3f3f3f3f
using namespace std;
int n,m,a[M];
struct node
{
int l,r,maxx;
}tre[M*4];
void push_up(int rt)
{
tre[rt].maxx=max(tre[ls(rt)].maxx,tre[rs(rt)].maxx);
}
void build(int rt,int l,int r)
{
tre[rt].l=l;
tre[rt].r=r;
if(l==r){
tre[rt].maxx=a[l];return;
}
int m=(l+r)>>1;
build(ls(rt),l,m);
build(rs(rt),m+1,r);
push_up(rt);
}
void add(int rt,int p,int v)
{
if(tre[rt].l==tre[rt].r){
tre[rt].maxx=v;
return ;
}
int m=(tre[rt].l+tre[rt].r)>>1;
if(p<=m) add(ls(rt),p,v);
else add(rs(rt),p,v);
push_up(rt);
}
int Query(int rt,int i,int j)
{
if(i<=tre[rt].l&&tre[rt].r<=j) return tre[rt].maxx;
int maxx=0;
int m=(tre[rt].l+tre[rt].r)>>1;
if(i<=m) maxx=max(maxx,Query(ls(rt),i,j));
if(m<j) maxx=max(maxx,Query(rs(rt),i,j));
return maxx;
}
int main()
{
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
build(1,1,n);
char str[10];
int i,j;
while(m--){
scanf("%s %d %d",str,&i,&j);
if(str[0]=='Q'){
printf("%d
",Query(1,i,j));
}
if(str[0]=='U'){
add(1,i,j);
}
}
}
return 0;
}</strong></span>