Luogu

算法

考虑只有宠物或者只有领养者。那么这个题跟营业额统计是一样的。

但是现在都有，所以考虑建两颗平衡树。

需要支持的操作：插入、删除、非严格前驱后继。

注意一开始插入INF和-INF（查询前驱后继的基本操作）

代码

#include <bits/stdc++.h>
#define re register
#define INF 0x3f3f3f3f
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

const int MAXN=80010;

struct fhq_treap {
    int ch[MAXN][2];
    int sz[MAXN],val[MAXN],rnd[MAXN];
    int cnt;
    
    inline void init() { cnt=0; }
    inline void pushup(int x) { sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; }
    inline int new_node(int x) { sz[++cnt]=1,val[cnt]=x,rnd[cnt]=rand(); return cnt; }
    
    inline void split(int now,int k,int& x,int& y) { //权值分裂
        if (!now) { x=y=0; return; }
        if (val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y);
        else y=now,split(ch[now][0],k,x,ch[now][0]);
        pushup(now);
    }
    inline int merge(int A,int B) {
        if (!A||!B) return A+B;
        if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B); pushup(A); return A; }
        else { ch[B][0]=merge(A,ch[B][0]); pushup(B); return B; }
    }
    inline int kth(int now,int k) {
        while (1) {
            if (k<=sz[ch[now][0]]) now=ch[now][0];
            else if (k==sz[ch[now][0]]+1) return now;
            else k-=sz[ch[now][0]]+1,now=ch[now][1];
        }
    }
    inline int getLast(int& now,int k) {
        int x,y; split(now,k,x,y);
        int ans=val[kth(x,sz[x])];
        now=merge(x,y);
        return ans;
    }
    inline int getNext(int& now,int k) {
        int x,y; split(now,k-1,x,y);
        int ans=val[kth(y,1)];
        now=merge(x,y);
        return ans;
    }
    inline void del(int& now,int k) {
        int x,y,z;
        split(now,k,x,z);
        split(x,k-1,x,y);
        y=merge(ch[y][0],ch[y][1]);
        now=merge(merge(x,y),z);
    }
    inline void insert(int& now,int k) {
        int x,y; split(now,k,x,y);
        now=merge(merge(x,new_node(k)),y);
    }
};

fhq_treap T1,T2; //T1是宠物，T2是领养者 
int R1,R2;

int main() {
    T1.init(); T2.init();
    int n=read(),ans=0;
    T1.insert(R1,-INF); T1.insert(R1,INF);
    T2.insert(R2,-INF); T2.insert(R2,INF);
    for (re int i=1;i<=n;i++) {
        int tp=read(),s=read();
        if (tp==0) {
            if (T2.sz[R2]==2) T1.insert(R1,s); //没人领了 
            else {
                int a=T2.getLast(R2,s),b=T2.getNext(R2,s);
                int la=s-a,lb=b-s;
                if (la<=lb) { ans+=la; T2.del(R2,a); }
                else { ans+=lb; T2.del(R2,b); }
            }
        }
        else if (tp==1) {
            if (T1.sz[R1]==2) T2.insert(R2,s);
            else {
                int a=T1.getLast(R1,s),b=T1.getNext(R1,s);
                int la=s-a,lb=b-s;
                if (la<=lb) { ans+=la; T1.del(R1,a); }
                else { ans+=lb; T1.del(R1,b); }
            }
        }
        (ans+=1000000)%=1000000;
    }
    printf("%d\n",ans);
    return 0;
}