P2286 [HNOI2004]宠物收养场

布满荆棘的人生 2023-06-04 08:00 185阅读 0赞

[**题目链接**][Link 1]

**这道题应该很快看出是平衡树吧。对于每次操作，相当于是在维护好的平衡树上找前驱和后继。一开始我想的是维护两棵平衡树，一棵宠物树，一棵是人树。但是我这样搞就非常傻逼，而且非常难调。其实只用维护一棵平衡树就够了，用一个变量来记录当前是宠物多还是人多，在树上查询前驱和后继就可以了。**

**坑点：**

**1.一开始要加入两个哨兵节点，不然容易出玄学错误。**

**2.求和的时候要加绝对值abs。**

**3.第八个点是0，但是我输出的是负数？？需要特判才能过。**

**代码：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    const int mod=1000000;
    const int inf=0x7fffffff;
    int n;
    int opt,a;
    int flag;
    long long sum;
    int fa1[maxn],key1[maxn],ch1[maxn][2],cnt1[maxn],siz1[maxn];
    int rt1,sz1;
    bool check1(int x){
        return ch1[fa1[x]][1]==x;
    }
    void pushup1(int x){
        siz1[x]=siz1[ch1[x][1]]+siz1[ch1[x][0]]+cnt1[x];
    }
    void clear1(int x){
        siz1[x]=cnt1[x]=fa1[x]=ch1[x][0]=ch1[x][1]=key1[x]=0;
    } 
    void rotate1(int x){
        int y=fa1[x],z=fa1[y],who=check1(x);
        ch1[y][who]=ch1[x][who^1];
        fa1[ch1[y][who]]=y;
        ch1[x][who^1]=y;
        fa1[y]=x,fa1[x]=z;
        if(z) ch1[z][ch1[z][1]==y]=x;
        pushup1(y);pushup1(x);
    }
    void splay1(int x,int goal){
        for(int f;(f=fa1[x])!=goal;rotate1(x)){
            if(fa1[f]!=goal) rotate1((check1(x)==check1(f))?f:x);
        }
        if(!goal) rt1=x;
    }
    void insert1(int x){
        if(!rt1){
            rt1=++sz1;
            cnt1[sz1]=siz1[sz1]=1;
            key1[sz1]=x;
            return;
        }
        int now=rt1,f=0;
        while(1){
            if(key1[now]==x){
                cnt1[now]++;
                pushup1(f);
                pushup1(now);
                splay1(now,0);
                return;
            }
            f=now,now=ch1[now][x>key1[now]];
            if(!now){
                sz1++;
                fa1[sz1]=f;
                ch1[f][x>key1[f]]=sz1;
                siz1[sz1]=cnt1[sz1]=1;
                key1[sz1]=x;
                pushup1(f);
                splay1(sz1,0);
                return;
            }
        }
    }
    int pre1(){
        int now=ch1[rt1][0];
        while(ch1[now][1]) now=ch1[now][1];
        return now;
    }
    int nxt1(){
        int now=ch1[rt1][1];
        while(ch1[now][0]) now=ch1[now][0];
        return now;
    }
    int rk1(int x){
        int now=rt1,ans=0;
        while(1){
            if(x<key1[now]) now=ch1[now][0];
            else{
                ans+=siz1[ch1[now][0]];
                if(x==key1[now]){
                    splay1(now,0);
                    return ans+1;
                }
                ans+=cnt1[now];
                now=ch1[now][1];
            }
        }
    } 
    void del1(int x){
        rk1(x);
        if(cnt1[rt1]>1){
            cnt1[rt1]--;
            pushup1(rt1);
            return;
        }
        if(!ch1[rt1][1]&&!ch1[rt1][0]){
            clear1(rt1);
            rt1=0;
            return;
        }
        if(!ch1[rt1][1]){
            int ort=rt1;
            rt1=ch1[rt1][0];
            fa1[rt1]=0;
            clear1(ort);
            return;
        }
        else if(!ch1[rt1][0]){
            int ort=rt1;
            rt1=ch1[rt1][1];
            fa1[rt1]=0;
            clear1(ort);
            return;
        }
        int ort=rt1,left=pre1();
        splay1(left,0);
        fa1[ch1[ort][1]]=rt1;
        ch1[rt1][1]=ch1[ort][1];
        clear1(ort);
        pushup1(rt1);
    }
    int tot;//判断宠物多还是人多 
    int main(){
        scanf("%d",&n);
        insert1(inf);
        insert1(-inf);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&opt,&a);
            if(!tot) insert1(a);
            if(tot>0){
         //pet
                if(opt==0) insert1(a);
                else{
                    insert1(a);
                    int ans1=key1[pre1()];
                    int ans2=key1[nxt1()];
                    if(abs(a-ans1)<=abs(ans2-a)){
                        sum=(long long)(sum+abs(a-ans1))%mod;
                        del1(ans1);
                    } 
                    else{
                        sum=(long long)(sum+abs(ans2-a))%mod;
                        del1(ans2);
                    } 
                    del1(a);
                }
            }
            if(tot<0){
         //customers
                if(opt==1) insert1(a);
                else{ 
                    insert1(a);
                    int ans1=key1[pre1()];
                    int ans2=key1[nxt1()];
                    if(abs(a-ans1)<=abs(ans2-a)){
                        sum=(long long)(sum+abs(a-ans1))%mod;
                        del1(ans1);
                    }
                    else{
                        sum=(long long)(sum+abs(ans2-a))%mod;
                        del1(ans2);
                    } 
                    del1(a);
                }
            }
            tot=tot+(opt==0?1:-1); 
        }
        if(sum<0) printf("0\n");//特判，不然有一个点会wa，我也不知道为什么 
        else printf("%lld\n",sum);
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11610909.html

[Link 1]: https://www.luogu.org/problem/P2286
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/1650cd186efe4b949ec6d231c74d725d.png