[HNOI2004]宠物收养所题解

╰+攻爆jí腚メ 2021-12-01 18:06 257阅读 0赞

# 一杯茶，一包烟，一道水题调一天 #

[题面][Link 1]

这题一眼看上去就是个裸板子对吧

本来以为要两棵splay，读了一下题发现店里只能有一种生物（人/宠物）

所以记录一下当前店里的状态就行了

老年手速20min过编译，

# 嗯？ #

检查了30min发现没取mod

# 嗯？ #

检查调试对拍了2h+30min重构代码

# 发现Splay打错了 #

int nxt()
    {
        if(cnt[root]>1)return root;
        int now=son[root][1];
        while(son[now][0])now=son[now][0];
        return now;
    }
    //√
    int nxt()
    {
        if(cnt[root]>1)return root;
        int now=son[root][1];
        while(son[now][1])now=son[now][0];
        return now;
    }
    //×

我打的时候在想什么啊啊啊啊啊身败名裂辽

总结：数据结构题如果迟迟调不过 不如检查一下是否在数据结构本身上犯了白痴错误

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    using namespace std;
    const int N=100005,mod=1e6,inf=0x3f3f3f3f;
    int fa[N],cnt[N],son[N][3],size[N],key[N],type,root;
    int n,num[3];
    void clear(int x)
    {
        fa[x]=cnt[x]=son[x][0]=son[x][1]=size[x]=key[x]=0;
    }
    bool judge(int x)
    {
        return son[fa[x]][1]==x;
    }
    void up(int x)
    {
        if(x)
        {
            size[x]=cnt[x];
            if(son[x][0])size[x]+=size[son[x][0]];
            if(son[x][1])size[x]+=size[son[x][1]];
        }
    }
    void rotate(int x)
    {
        int old=fa[x],oldf=fa[old],lr=judge(x);
        son[old][lr]=son[x][lr^1];
        fa[son[old][lr]]=old;
        son[x][lr^1]=old;
        fa[old]=x;
        fa[x]=oldf;
        if(oldf)son[oldf][son[oldf][1]==old]=x;
        up(old);up(x);
    }
    void splay(int x)
    {
        for(int f;f=fa[x];rotate(x))
            if(fa[f])rotate(judge(x)==judge(f)?f:x);
        root=x;
    }
    void ins(int x)
    {
        if(!root)
        {
            type++;
            key[type]=x;
            root=type;
            cnt[type]=size[type]=1;
            fa[type]=son[type][0]=son[type][1]=0;
            return ;
        }
        int now=root,f=0;
        while(1)
        {
            if(x==key[now])
            {
                cnt[now]++;
                up(now);
                up(f);
                splay(now);
                return ;
            }
            f=now;now=son[now][key[now]<x];
            if(!now)
            {
                type++;
                size[type]=cnt[type]=1;
                son[type][0]=son[type][1]=0;
                son[f][x>key[f]]=type;
                fa[type]=f;
                key[type]=x;
                up(f);splay(type);
                return ;
            }
        }
    }
    int pre()
    {
        if(cnt[root]>1)return root;
        int now=son[root][0];
        while(son[now][1])now=son[now][1];
        return now;
    }
    int nxt()
    {
        if(cnt[root]>1)return root;
        int now=son[root][1];
        while(son[now][0])now=son[now][0];
        return now;
    }
    void changeroot(int x)
    {
        int now=root;
        while(1)
        {
            if(x<key[now])now=son[now][0];
            else 
            {
                if(x==key[now])
                {
                    splay(now);
                    return ;
                }
                now=son[now][1];
            }
        }
    }
    void del(int x)
    {
        changeroot(x);
        if(cnt[root]>1)
        {
            cnt[root]--;
            up(root);
            return ;
        }
        if(!son[root][0]&&!son[root][1])
        {
            clear(root);
            root=0;
            return ;
        }
        if(!son[root][0])
        {
            int old=root;
            root=son[root][1];
            fa[root]=0;
            clear(old);
            return ;
        }
        else if(!son[root][1])
        {
            int old=root;
            root=son[root][0];
            fa[root]=0;
            clear(root);
            return ;
        }
        int old=root,L=pre();
        splay(L);
        son[root][1]=son[old][1];
        fa[son[old][1]]=root;
        clear(old);
        up(root);
    }
    inline int read()
    {
        int x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9')
        {
         if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9')
        {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return x*f;
    }
    int now_=-1;
    int ans;
    int main()
    {
        n=read();
        ins(inf);ins(-inf);
        for(int i=1;i<=n;i++)
        {
            int op=read(),val=read();
            //cout<<"root="<<root<<endl;
            if(now_==-1)
            {
                now_=op;
                ins(val);
                num[op]++;
                continue;
            }
            if(now_==op)
            {
                ins(val);
                num[op]++;
                continue;
            }
            ins(val);
            int pre_=pre(),nxt_=nxt(),preval=key[pre_],nxtval=key[nxt_];
            del(val);
            if(val-preval<=nxtval-val)ans+=(val-preval)%mod,del(preval),num[op^1]--;
            else ans+=(nxtval-val)%mod,del(nxtval),num[op^1]--;
            if(num[0]==0&&num[1]==0)now_=-1;
            ans%=mod;
        }
        cout<<ans%mod<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Rorschach-XR/p/11014043.html

[Link 1]: https://loj.ac/problem/10144