HDU 1754 线段树 - c++编程基础

[cpp]

#include

#define Lson left , t , rt<<1

#define Rson t+1 ,right,rt<<1|1

using namespace std;

const int maxn=200005;

int f[maxn<<2];

void PushUP( int rt ){

f[rt] = max( f[rt<<1], f[rt<<1|1] );

}

void build( int left, int right ,int rt ){

if( left==right ){

cin>>f[rt];

return;

}

int t=(left + right)>>1;

build(Lson);

build(Rson);

PushUP(rt);

}

void update(int ii,int value,int left, int right, int rt ){

if( left == right ){

f[rt] = value; return;

}

int t=(left+right)>>1;

if(ii<=t) update(ii, value, Lson);

else update(ii, value, Rson);

PushUP(rt);

}

int query(int l, int r, int left, int right, int rt ){

if( l<=left && r>=right )

return f[rt];

int t=(left+right)/2;

int ret = 0;

if(l <= t)ret = max(ret, query( l, r, Lson) );

if(r > t) ret = max(ret, query( l, r, Rson) );

return ret;

}

int main(){

int n,m;

while(cin>>n>>m){

build(1,n,1);

while(m--){

char C; int a,b;//for(int i=0;i<=n;++i)cout<

cin>>C>>a>>b;

if(C=='Q') cout<

else update(a,b,1,n,1);

}

return 0;

}