bzoj 1208: [HNOI2004]宠物收养所

今天药忘吃喽~ 2021-09-29 15:32 276阅读 0赞

替罪羊树是个好东西

/**************************************************************
        Problem: 1208
        User: lxy8584099
        Language: C++
        Result: Accepted
        Time:472 ms
        Memory:5056 kb
    ****************************************************************/
     
    /*
        维护两个平衡树
        人多的时候再宠物平衡树里面找
        宠物多的时候再人平衡树里面找
    */
    #include<cstdio>
    #define lc (c[k][x][0])
    #define rc (c[k][x][1])
    #define inf (2147483647)
    using namespace std;
    const int N=8e4+50;
    const double xxx=0.75;
    int tot[2],root[2],num[2],n,top,res;
    struct tree
    {
        int fa[2][N],c[2][N][2],val[2][N],size[2][N],sum[2][N],sta[N];
        bool exist[2][N];
        inline void pushup(int k,int x)
        {
            size[k][x]=exist[k][x],sum[k][x]=1;
            if(lc) size[k][x]+=size[k][lc],sum[k][x]+=sum[k][lc];
            if(rc) size[k][x]+=size[k][rc],sum[k][x]+=sum[k][rc];
        }
        inline int build(int k,int l,int r)
        {
            if(l>r) return 0; int mid=(l+r)>>1,x=sta[mid];
            fa[k][lc=build(k,l,mid-1)]=fa[k][rc=build(k,mid+1,r)]=x;
            pushup(k,x); return x;
        }
        inline bool needpia(int k,int x)
        {
            return xxx*sum[k][x]<sum[k][lc]||xxx*sum[k][x]<sum[k][rc];
        }
        inline void pia(int k,int x)
        {
            if(lc) pia(k,lc); sta[++top]=x; if(rc) pia(k,rc);
        }
        inline void rebuild(int k,int x)
        {
            int flag=(x==root[k]); top=0,pia(k,x);
            int f=fa[k][x],s=(c[k][f][1]==x);
            x=build(k,1,top); c[k][fa[k][x]=f][s]=x;
            while(f) pushup(k,f),f=fa[k][f]; 
            if(flag) root[k]=x;
        }
        inline void insert(int k,int v)
        {
            int x=root[k],rt=++tot[k];val[k][rt]=v;
            c[k][rt][1]=c[k][rt][0]=0;
            size[k][rt]=sum[k][rt]=exist[k][rt]=1;
            if(!root[k]) {root[k]=rt;fa[k][rt]=0;return ;}
            while(1)
            {
                size[k][x]++;sum[k][x]++;
                int s=(v>=val[k][x]);
                if(c[k][x][s]) x=c[k][x][s];
                else {fa[k][c[k][x][s]=rt]=x;break;}
            }
            int flag=0;
            for(x=rt;x;x=fa[k][x]) if(needpia(k,x)) flag=x;
            if(flag) rebuild(k,flag);
        }
        inline int rank(int k,int v)
        {
            int res=1,x=root[k];
            while(x)
            {
                if(v<=val[k][x]) x=lc;
                else res+=size[k][lc]+exist[k][x],x=rc;
            } return res;
        }
        inline int kth(int k,int K) 
        {
            int x=root[k];
            while(1)
            {
                if(K==size[k][lc]+1&&exist[k][x]) return val[k][x];
                if(K<=size[k][lc]) x=lc;
                else K-=size[k][lc]+exist[k][x],x=rc;
            }
        }
        inline void erase(int k,int v)
        {
            int x=root[k],K=rank(k,v);
            while(1)
            {
                size[k][x]--;
                if(K==size[k][lc]+1&&exist[k][x]) {exist[k][x]=0;break;}
                if(K<=size[k][lc]) x=lc;
                else K-=size[k][lc]+exist[k][x],x=rc;
            }
            if(needpia(k,root[k])) rebuild(k,root[k]);
        }
    }T;
    inline int abs(int x){
        return x>0?x:-x;}
    int main()
    {
        T.insert(0,-inf);T.insert(1,-inf);
        T.insert(0,inf);T.insert(1,inf);
        scanf("%d",&n);while(n--)
        {
            int k,a;scanf("%d%d",&k,&a);
            if(!num[!k]) num[k]++,T.insert(k,a);
            else
            {
                num[!k]--;
                int f1=T.kth(!k,T.rank(!k,a)-1),
                    f2=T.kth(!k,T.rank(!k,a+1));
                if(abs(f1-a)>abs(f2-a)||f1==-inf) f1=f2;
                T.erase(!k,f1);
                (res+=abs(f1-a))%=1000000;
            }
        }
        printf("%d\n",res);
        return 0;
    }

转载于:https://www.cnblogs.com/lxy8584099/p/10432815.html