我是题面

题意简单明了，两种数，如果加入一个数的时候有另一种数还存在，那就取出另一种数中与这个数差值的绝对值最小的将其删除（多个则取较小），并对答案产生它们差值的绝对值的贡献，如果没有另一种数存在，那就先将这个数存下

平衡树裸题，直接两个平衡树维护就ok了，一个也能维护，稍麻烦一点

线段树好像也可做，我没写，应该不难

我写的是Splay，把Splay用结构体封装好，开两个Splay异常好写

下面放代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc getchar
#define maxn 80005
#define mo 1000000
using namespace std;

inline ll read(){
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}int n;ll ans;

struct ahaha{  //Splay的结构体
    struct ahaha1{
        int sz,cnt,ch[2];ll v;
    }t[maxn];int rt,tot,f[maxn];
    #define lc t[i].ch[0]
    #define rc t[i].ch[1]
    inline int get(int i){return i==t[f[i]].ch[1];}
    inline void update(int i){
        t[i].sz=t[i].cnt+t[lc].sz+t[rc].sz;
    }
    inline void del(int i){
        t[i].v=t[i].sz=t[i].cnt=f[i]=0;
    }
    inline int newnode(ll v){
        int i=++tot;
        t[i].sz=t[i].cnt=1;t[i].v=v;
        return i;
    }
    inline void rotate(int x){
        int y=f[x],z=f[y],k=get(x);
        f[x]=z;f[t[x].ch[k^1]]=y;f[y]=x;
        if(z)t[z].ch[y==t[z].ch[1]]=x;
        t[y].ch[k]=t[x].ch[k^1];t[x].ch[k^1]=y;
        update(y);update(x);
    }
    void Splay(int x){
        for(int y=f[x];f[x];rotate(x),y=f[x]){
            if(f[y])rotate(get(x)==get(y)?y:x);
            rt=x;
        }
    }
    void insert(ll v){
        int i=rt,k;
        if(!rt){rt=newnode(v);return;}
        while(1){
            k=v>t[i].v;
            if(v==t[i].v){
                ++t[i].sz;++t[i].cnt;
                Splay(i);return;
            }
            if(!t[i].ch[k]){
                t[i].ch[k]=newnode(v);f[t[i].ch[k]]=i;
                Splay(t[i].ch[k]);return;
            }
            i=t[i].ch[k];
        }
    }
    void find(ll v){
        int i=rt;
        while(1){
            if(v<t[i].v){
                i=lc;
                if(!i)return;
            }
            else{
                if(!rc||v==t[i].v){
                    Splay(i);return ;
                }
                i=rc;
            }
        }
    }
    inline void earase(ll v){
        find(v);int old=rt,i=rt;
        if(t[rt].cnt!=1){--t[rt].cnt;return;}
        if(t[rt].sz==1){del(rt);rt=0;return;}
        if(!lc){rt=rc;f[rt]=0;del(old);return;}
        if(!rc){rt=lc;f[rt]=0;del(old);return;}
        i=lc;while(rc)i=rc;Splay(i);
        t[rt].ch[1]=t[old].ch[1];f[t[rt].ch[1]]=rt;
        del(old);update(rt);
    }
    ll pre(ll v){
        int i=rt;ll maxa=-1;
        while(i){
            if(t[i].v==v)return v;
            if(t[i].v<v){
                maxa=max(maxa,t[i].v);
                i=rc;
            }
            else i=lc;
        }
        return maxa;
    }
    ll next(ll v){
        int i=rt;ll mina=2147483649;
        while(i){
            if(t[i].v==v)return v;
            if(t[i].v>v){
                mina=min(mina,t[i].v);
                i=lc;
            }
            else i=rc;
        }
        return mina;
    }
}t1,t2;

inline void solve_1(){
    ll v=read();
    if(!t2.rt)  //如果没有另一种数，先存起来
        t1.insert(v);
    else{
        ll pre=t2.pre(v),next=t2.next(v); //查询前后缀，没有前缀则前缀为-1，没有后缀则后缀为2147483649
        if(pre==-1){
            ans=(ans+next-v)%mo;
            t2.earase(next);return;
        }
        if(next==2147483649){
            ans=(ans+v-pre)%mo;
            t2.earase(pre);return;
        }
        if(v-pre<=next-v){   //按照题意取较小，然后删除就可以了
            ans=(ans+v-pre)%mo;
            t2.earase(pre);return;
        }
        else{
            ans=(ans+next-v)%mo;
            t2.earase(next);return;
        }
    }
}
inline void solve_2(){  //同上
    ll v=read();
    if(!t1.rt)
        t2.insert(v);
    else{
        ll pre=t1.pre(v),next=t1.next(v);
        if(pre==-1){
            ans=(ans+next-v)%mo;
            t1.earase(next);return;
        }
        if(next==2147483649){
            ans=(ans+v-pre)%mo;
            t1.earase(pre);return;
        }
        if(v-pre<=next-v){
            ans=(ans+v-pre)%mo;
            t1.earase(pre);return;
        }
        else{
            ans=(ans+next-v)%mo;
            t1.earase(next);return;
        }
    }
}

int main(){
    n=read();
    while(n--){
        int zz=read();
        switch(zz){
            case 0:solve_1();break;
            case 1:solve_2();break;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

不要抄代码哦