fhq treap

开俩哨兵节点，然后插入、删除、前驱、后继，统计即可

#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"#include"ctime"using namespace std;const int MAXN=8e4+5;const int MOD=1e6;int n,cnt,root,co;bool kd;long long ans;int siz[MAXN],sn[MAXN][2],rev[MAXN];long long val[MAXN];int cret(long long v){    siz[++cnt]=1;    val[cnt]=v;    rev[cnt]=rand();    return cnt;}int un(int x,int y){    if(!x||!y) return x|y;    if(rev[x]<=rev[y]){        sn[x][1]=un(sn[x][1],y);        siz[x]=siz[sn[x][0]]+siz[sn[x][1]]+1;        return x;    }sn[y][0]=un(x,sn[y][0]);    siz[y]=siz[sn[y][0]]+siz[sn[y][1]]+1;    return y;}void dro(int k,int v,int &x,int &y){    if(!k){x=y=0;return;}    if(val[k]<=v) x=k,dro(sn[k][1],v,sn[k][1],y);    else y=k,dro(sn[k][0],v,x,sn[k][0]);    siz[k]=siz[sn[k][0]]+siz[sn[k][1]]+1;    return;}int rnk(int k,int v){    if(sn[k][0]==k) return n+1;    if(v<=siz[sn[k][0]]) return rnk(sn[k][0],v);    if(v==siz[sn[k][0]]+1) return k;    return rnk(sn[k][1],v-siz[sn[k][0]]-1);}void ins(int v){    int x,y;    dro(root,val[v],x,y);    root=un(un(x,v),y);    return;}void del(int v){    int x,y,z,c;    dro(root,v,x,z),dro(x,v-1,x,y);c=y;    y=un(sn[y][0],sn[y][1]);sn[c][0]=sn[c][1]=val[c]=siz[c]=0;    root=un(un(x,y),z);    return;}void debug(){    for(int i=1;i<=siz[root];++i) printf("%d ",val[rnk(root,i)]);    puts("-");}int main(){    scanf("%d",&n);    int ct1=cret((long long)-1e10),ct2=cret((long long)1e10);    ins(ct1);ins(ct2);    while(n--){        int c,v;scanf("%d%d",&c,&v);        if(!co||kd==c){            kd=c;++co;            int ct=cret(v);            ins(ct);        }else{            int x,y;--co;            dro(root,v,x,y);            long long ct1=val[rnk(x,siz[x])],ct2=val[rnk(y,1)];            root=un(x,y);            if(abs(ct1-v)<=abs(ct2-v)) del(ct1),ans=(ans+abs(ct1-v))%MOD;            else del(ct2),ans=(ans+abs(ct2-v))%MOD;        }    }printf("%lld\n",ans);    return 0;}