[HNOI2004]宠物收养场

平衡树模板题，set也能做。
求个前驱后继，按照题目上说的做就行了。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>
using namespace std;
const int N=200000,mod=1000000;
int ch[N][2],fa[N],siz[N],cnt[N],prio[N],rt,tot,ans,n;
long long val[N];
inline void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}
bool is_right(int x) {return x==ch[fa[x]][1];}
inline void rotate(int &x,int tag) {
    int y=ch[x][tag^1];
    ch[x][tag^1]=ch[y][tag];
    ch[y][tag]=x;
    siz[y]=siz[x];
    pushup(x);
    x=y;
}
void insert(int &x,long long k) {
     if(x==0) {x=++tot;val[x]=k,prio[x]=rand(),siz[x]=cnt[x]=1;return;}
     siz[x]++;
     if(k<val[x]) {insert(ch[x][0],k);if(prio[ch[x][0]]<prio[x]) rotate(x,1);}
     else if(k>val[x]) {insert(ch[x][1],k);if(prio[ch[x][1]]<prio[x]) rotate(x,0);}
     else if(k==val[x]) cnt[x]++;
}
void del(int &x,long long k) {
    if(x==0) return;
    if(val[x]==k) {
        if(cnt[x]>1) {cnt[x]--,siz[x]--;return;}
        if(ch[x][0]==0||ch[x][1]==0) {x=ch[x][0]+ch[x][1];return;}
        if(prio[ch[x][0]]<prio[ch[x][1]]) rotate(x,1),del(x,k);
        else rotate(x,0),del(x,k);
        return;
    }
    if(val[x]<k) {
        siz[x]--;
        del(ch[x][1],k);
    }
    else if(val[x]>k) {
        siz[x]--;
        del(ch[x][0],k);
    }
    pushup(x);
}
int rnk(int x,long long  k) {
    if(x==0) return 0;
    if(val[x]==k) return siz[ch[x][0]]+1;
    if(val[x]<k) return rnk(ch[x][1],k)+siz[ch[x][0]]+cnt[x];
    if(val[x]>k) return rnk(ch[x][0],k);
}
int getval(int x,long long k) {
    if(x==0) return 0;
    if(k<=siz[ch[x][0]]) return getval(ch[x][0],k);
    if(siz[ch[x][0]]+cnt[x]<k) return getval(ch[x][1],k-siz[ch[x][0]]-cnt[x]);
    return val[x];
}
void pre(int x,long long k) {
    if(!x) return;
    if(val[x]==k) {ans=x;return;}
    if(val[x]<k) ans=x,pre(ch[x][1],k);
    else pre(ch[x][0],k);
}
void nxt(int x,long long k) {
    if(!x) return;
    if(val[x]==k){ans=x;return;}
    if(val[x]>k) ans=x,nxt(ch[x][0],k);
    else nxt(ch[x][1],k);
}
int pet,pers;
int main() {
    scanf("%d",&n);
    srand(19260817);
    
    insert(rt,-(1ll<<60));
    insert(rt,1ll<<60);
    int opt,x,sum=0;
    while(n--) {
        scanf("%d%d",&opt,&x);ans=0;
        if(opt==1) {
            if(pet) {
                pet--;            
                pre(rt,x);
                int tp1=val[ans];
                nxt(rt,x);
                int tp2=val[ans];
                if(tp1*tp2==0&&tp1+tp2) sum+=abs(x-tp1-tp2),del(rt,tp1+tp2);
                else if(abs(tp1-x)==abs(tp2-x)) sum+=abs(tp1-x),del(rt,min(tp1,tp2));
                else if(abs(tp1-x)>abs(tp2-x)) sum+=abs(tp2-x),del(rt,tp2);
                else sum+=abs(tp1-x),del(rt,tp1);
                sum%=mod;
            }
            else {pers++;insert(rt,x);}
        }
        else {
            if(pers) {
                pers--;
                pre(rt,x);
                int tp1=val[ans];
                nxt(rt,x);
                int tp2=val[ans];
                if(tp1*tp2==0&&tp1+tp2) sum+=abs(x-tp1-tp2),del(rt,tp1+tp2);
                else if(abs(tp1-x)==abs(tp2-x)) sum+=abs(tp1-x),del(rt,min(tp1,tp2));
                else if(abs(tp1-x)>abs(tp2-x)) sum+=abs(tp2-x),del(rt,tp2);
                else sum+=abs(tp1-x),del(rt,tp1);
                sum%=mod;
            }
            else {pet++;insert(rt,x);}
        }
    }
    cout<<sum;
}