首页 > 代码库 > hdu 1754 I Hate It(单点更新,区段查最值)

hdu 1754 I Hate It(单点更新,区段查最值)

题意:

N个成绩。M个操作。

Q a b:查询第a个到第b个成绩中最高成绩

U a b:将第a个成绩改成b

 

思路:

看代码,,

 

代码:

const int maxn = 200010;int maxs[maxn<<2];int N,M;void PushUp(int rt){    maxs[rt] = max( maxs[rt<<1], maxs[rt<<1|1] );}void build(int l,int r,int rt){    if(l==r){        scanf("%d",&maxs[rt]);        return;    }    int m = (l + r) >> 1;    build(lson);    build(rson);    PushUp(rt);}void update(int p,int add,int l,int r,int rt){    if(l==r){        maxs[rt] = add;        return;    }    int m = (l + r) >> 1;    if(p <= m) update(p,add,lson);    else update(p,add,rson);    PushUp(rt);}int query(int L,int R,int l,int r,int rt){    if(L<=l && r<=R){        return maxs[rt];    }    int m = (l + r) >> 1;    int ret = 0;    if(L <= m) ret = max( ret, query(L,R,lson) );    if(R > m) ret = max( ret, query(L,R,rson) );    return ret;}int main(){    while(scanf("%d%d",&N,&M)!=EOF){        build(1,N,1);        for(int i=1;i<=M;++i){            char c;            int a,b;            getchar();            scanf("%c%d%d",&c,&a,&b);            if(c == Q) printf("%d\n",query(a,b,1,N,1));            else if(c == U) update(a,b,1,N,1);        }    }}

 

hdu 1754 I Hate It(单点更新,区段查最值)