1754.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<cstdio>
#include<string>
struct tree{
    int l,r,v;
    tree *lchild,*rchild;
};
tree mem[400010];
int score[200010];
int pos;
tree *new_tree(){
    tree *pt=&mem[pos++];
    memset(pt,0,sizeof(pt));
    return pt;
}
tree *make_tree(int le,int ri){
    //注意把score的值加入线段树的办法
    tree *root=new_tree();
    root->l=le;root->r=ri;
    if(ri-le<=1)//递规终点
        root->v=score[root->l]>score[root->r]?score[root->l]:score[root->r];
    else{
        int mid=(le+ri)>>1;
        root->lchild=make_tree(le,mid);
        root->rchild=make_tree(mid,ri);
        root->v=root->lchild->v>root->rchild->v?root->lchild->v:root->rchild->v;
    }
    return root;
}
int getmax(tree *root,int le,int ri){
    if(root->l==le&&root->r==ri)
        return root->v;
    else{
        int mid=(root->l+root->r)>>1;
        if(le>=mid)//范围在右子树上
            return getmax(root->rchild,le,ri);//我写成：getmax(root->rchild,mid,ri)
        else if(ri<=mid)//范围在左子树上
            return getmax(root->lchild,le,ri);//我写成：getmax(root->rchild,le,mid)
        //在哪个分支上，就在哪棵树上继续搜
        else{
            //分半搜
            int t1=getmax(root->lchild,le,mid);
            int t2=getmax(root->rchild,mid,ri);
            return t1>t2?t1:t2;
        }
    }
}
void update(tree *root,int id){
    if(root->lchild==NULL&&root->rchild==NULL){
        root->v=score[root->l]>score[root->r]?score[root->l]:score[root->r];
        return;
    }
    int mid=(root->l+root->r)>>1;
    if(id<=mid)//在左树上，更新左树
        update(root->lchild,id);
    if(id>=mid)//在右树上，更新右树
        update(root->rchild,id);
    //较大值
    root->v=root->lchild->v>root->rchild->v?root->lchild->v:root->rchild->v;
    return;
}
void main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        for(int i=1;i<=n;i++)
            scanf("%d",&score[i]);
        getchar();
        pos=0;
        tree *T=make_tree(1,n);
        while(m--){
            char cmd;
            int left,right;
            scanf("%c%d%d",&cmd,&left,&right);
            getchar();
            if(cmd=='Q'){
                if(left==right)
                    printf("%d\n",score[left]);
                else
                    printf("%d\n",getmax(T,left,right));
            }
            else if(cmd=='U'){
                score[left]=right;
                update(T,left);
            }
        }
    }
}