【Splay】 1208 [HNOI2004]宠物收养所

/**************************************************************
    Problem: 1208
    User: 704035233
    Language: C++
    Result: Accepted
    Time:136 ms
    Memory:3236 kb
****************************************************************/
 
#include<cstdio>
#include<iostream>
#define rep(i,n) for(int i=1 ;i <=n;i++)
using namespace std;
const int mo=1000000;
const int maxn=80010;
const int INF=1<<31-1;
struct Node
{
    int num,key,Size,fa;
    int son[2];
}Tree[maxn];
 
inline int read(){
    static int r, sign;
    static char c;
    r = 0, sign = 1;
    do c = getchar(); while(c != '-' && (c < '0' || c > '9'));
    if( c == '-')sign = -1, c = getchar();
    while( c >= '0' && c <='9') r = r*10 +(int)(c - '0'), c = getchar();
    return sign * r;
}
int root,tot=0,n,m,cnt,x;
inline void Updata(int x)
{
    Tree[x].Size=Tree[Tree[x].son[0]].Size+Tree[Tree[x].son[1]].Size+Tree[x].num;
}
inline void Push_Down(int x)
{
 
}
 
inline void Rotate(int x,int c)
{
    int y=Tree[x].fa;
    Push_Down(y);Push_Down(x);
    Tree[y].son[!c]=Tree[x].son[c];
    if(Tree[x].son[c])Tree[Tree[x].son[c]].fa=y;
    Tree[x].fa=Tree[y].fa;
    if(Tree[y].fa)
        Tree[Tree[y].fa].son[Tree[Tree[y].fa].son[1]==y]=x;
    Tree[x].son[c]=y;Tree[y].fa=x;
    Updata(y);Updata(x);
    if(Tree[x].fa==0)root=x;
}
inline void Splay(int x,int f)
{
    Push_Down(x);
    while(Tree[x].fa!=f)
    {
        if(Tree[Tree[x].fa].fa==f)
            Rotate(x,Tree[Tree[x].fa].son[0]==x);
        else
        {
            int y=Tree[x].fa;
            int kind=Tree[Tree[y].fa].son[1]==y;
            if(Tree[y].son[kind]==x)
                Rotate(y,!kind) , Rotate(x,!kind);
            else
                Rotate(x,kind)  , Rotate(x,!kind);
        }
    }
    if(f==0)root=x;
    Updata(x);
}
inline void Insert(int val,int x){
    if(!x)
    {
        root=++tot;
        Tree[tot].key=val;Tree[tot].fa=0;Tree[tot].num=Tree[tot].Size=1;
        return;
    }
    if(val==Tree[x].key)
    {
        Tree[x].num++;
        Updata(x);
        Splay(x,0);
        return;
    }
    if(!Tree[x].son[val>Tree[x].key])
    {
        Tree[x].son[val>Tree[x].key]=++tot;
        Tree[tot].key=val;Tree[tot].num=Tree[tot].Size=1;Tree[tot].fa=x;
        Updata(x);
        Splay(tot,0);
        return;
    }
    Insert(val,Tree[x].son[val>Tree[x].key]);
    Updata(x);
}
 
inline int Find_pre(int x)
{
    if(Tree[x].num>1)return Tree[x].key;
    int Nex=Tree[x].son[0];
    if(!Nex)return -INF;
    while(Tree[Nex].son[1])Nex=Tree[Nex].son[1];
    return Tree[Nex].key;
}
 
inline int Find_succ(int x)
{
    if(Tree[x].num>1)return Tree[x].key;
    int Nex=Tree[x].son[1];
    if(!Nex)return INF;
    while(Tree[Nex].son[0])Nex=Tree[Nex].son[0];
    return Tree[Nex].key;
}
 
inline int Find(int x,int f)
{
    while(Tree[f].key!=x && Tree[f].son[x>Tree[f].key])f=Tree[f].son[x>Tree[f].key];
    Splay(f,0);
    if(Tree[f].key!=x){
        return -1;
    }
    return f;
}
inline bool Delete(int x,int f)
{
    int k=Find(x,root);
    if(k==-1)return 0;
    if(Tree[k].num>1)
    {
        Tree[k].num--;
        Updata(k);
    }
    else
    {
        if(!Tree[k].son[0]){
                root=Tree[k].son[1];
                Tree[root].fa=0;
        }
        else
        {
            int Nex=Tree[k].son[0];
            Tree[Nex].fa=0;
            while(Tree[Nex].son[1])Nex=Tree[Nex].son[1];
            Splay(Nex,0);
            Tree[root].son[1]=Tree[k].son[1];
            Tree[Tree[k].son[1]].fa=root;
            Updata(root);
        }
    }
    return 1;
}
inline void Travel(int x)
{
    if(Tree[x].son[0])Travel(Tree[x].son[0]);
    rep(i,Tree[x].num)printf("%d ",Tree[x].key);
    if(Tree[x].son[1])Travel(Tree[x].son[1]);
}
int main()
{
    n=read();
    int sumren=0,sumpet=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        cnt=read(),x=read();
        {
            if(cnt==0)
            {
                if(sumren==0)
                {
                    Insert(x,root);
                    sumpet++;
                }
                else
                {
                    Insert(x,root);
                    int Pre=Find_pre(root),Succ=Find_succ(root);
                    bool flag=Delete(x,root);
                    if(x-Pre<=Succ-x)
                    {
                        ans+=x-Pre;
                        ans%=mo;
                        Delete(Pre,root);
                    }
                    else
                    {
                        ans+=Succ-x;
                        ans%=mo;
                        Delete(Succ,root);
                    }
                    sumren--;
                }
            }
            else
            {
                if(sumpet==0)
                {
                    Insert(x,root);
                    sumren++;
                }
                else
                {
                    Insert(x,root);
                    int Pre=Find_pre(root),Succ=Find_succ(root);
 
                    bool flag=Delete(x,root);
                    if(x-Pre<=Succ-x)
                    {
                        ans+=x-Pre;
                        ans%=mo;
                        Delete(Pre,root);
                    }
                    else
                    {
                        ans+=Succ-x;
                        ans%=mo;
                        Delete(Succ,root);
                    }
                    sumpet--;
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}