BZOJ 2333 左偏树（写得我人生都崩溃了...）

浅浅的花香味﹌ 2021-10-01 03:26 184阅读 0赞

思路：

高一神犇 竟然 问我这道题   我光荣地  看着题解（划掉）  写了一下午 QaQ

multiset不能erase(一个值)   这样就把等于这个值 的数都erase掉了  （woc我一开始不知道啊啊啊 ）

注意细节...

//By SiriusRen
    #include <set>
    #include <cstdio>
    using namespace std;
    const int N=300050;
    int n,q,all,xx,yy;
    char op[3];
    struct Tree{
        int w,l,r,fa,dis,lazy;}tr[N];
    int find(int x){
        while(tr[x].fa)x=tr[x].fa;return x;}
    void push_down(int x){
        if(tr[x].l)tr[tr[x].l].w+=tr[x].lazy,tr[tr[x].l].lazy+=tr[x].lazy;
        if(tr[x].r)tr[tr[x].r].w+=tr[x].lazy,tr[tr[x].r].lazy+=tr[x].lazy;
        tr[x].lazy=0;
    }
    int merge(int x,int y){
        if(x*y==0)return x+y;
        if(tr[x].w<tr[y].w)swap(x,y);
        push_down(x);
        tr[x].r=merge(tr[x].r,y);
        tr[tr[x].r].fa=x;
        if(tr[tr[x].l].dis<tr[tr[x].r].dis)swap(tr[x].l,tr[x].r);
        tr[x].dis=tr[tr[x].r].dis+1;
        return x;
    }
    int del(int x){
        int F=tr[x].fa,t;
        push_down(x);tr[t=merge(tr[x].l,tr[x].r)].fa=F;
        tr[x].l=tr[x].r=tr[x].fa=tr[x].dis=0;
        if(tr[F].l==x)tr[F].l=t;
        else tr[F].r=t;
        while(tr[t].fa)t=tr[t].fa;
        return find(t);
    }
    void dfs(int x){
        if(tr[x].fa)dfs(tr[x].fa);
        push_down(x);
    }
    multiset<int>s;multiset<int>::iterator it;
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&tr[i].w),s.insert(tr[i].w);
        scanf("%d",&q);
        for(int I=1;I<=q;I++){
            scanf("%s",op);
            if(op[0]=='A'){
                if(op[1]=='1'){
                    scanf("%d%d",&xx,&yy);
                    dfs(xx);
                    s.erase(s.find(tr[find(xx)].w));
                    tr[xx].w+=yy;
                    s.insert(tr[merge(del(xx),xx)].w);
                }
                else if(op[1]=='2'){
                    scanf("%d%d",&xx,&yy);
                    int fx=find(xx);
                    s.erase(s.find(tr[fx].w));
                    tr[fx].w+=yy,tr[fx].lazy+=yy;
                    s.insert(tr[fx].w);
                }
                else if(op[1]=='3')scanf("%d",&xx),all+=xx;
            }
            else if(op[0]=='F'){
                if(op[1]=='1'){
                    scanf("%d",&xx);dfs(xx);
                    printf("%d\n",tr[xx].w+all);
                }
                else if(op[1]=='2'){
                    scanf("%d",&xx);
                    printf("%d\n",tr[find(xx)].w+all);
                }
                else if(op[1]=='3'){
                    it=s.end();it--;
                    printf("%d\n",(*it)+all);
                }
            }
            else{
                scanf("%d%d",&xx,&yy);
                int fx=find(xx),fy=find(yy);
                if(fx!=fy){
                    if(merge(fx,fy)==fy)s.erase(s.find(tr[fx].w));
                    else s.erase(s.find(tr[fy].w));
                }
            }
        }
    }

转载于:https://www.cnblogs.com/SiriusRen/p/6637659.html