BZOJ 1208 [HNOI2004] 애완동물 입양소 트랩

제목: 너무 길어서 자기를 개괄하기 힘들죠.해석: 선구자를 찾는 작업이 분명히 있습니다.바로 Treap에 올라가면 돼요. 복잡도도 넓게 놓지만 Treap에 현재 존재하는 애완동물인지 입양인인지 기록하면 돼요.토론해 보면 sb문제야.코드:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 80010
#define mod 1000000 
#define INF 0x7fffffff
using namespace std;
int n,size;
int ans;
int root;
struct node
{
    int l,r,val,siz,rnd;
}tr[N];
void pushup(int rt)
{
    tr[rt].siz=tr[tr[rt].l].siz+tr[tr[rt].r].siz+1;
}
void lturn(int &rt)
{
    int t=tr[rt].r;
    tr[rt].r=tr[t].l;
    tr[t].l=rt;
    tr[t].siz=tr[rt].siz;
    pushup(rt);
    rt=t;
}
void rturn(int &rt)
{
    int t=tr[rt].l;
    tr[rt].l=tr[t].r;
    tr[t].r=rt;
    tr[t].siz=tr[rt].siz;
    pushup(rt);
    rt=t;
}
void insert(int &rt,int v)
{
    if(!rt)
    {
        rt=++size;
        tr[rt].l=tr[rt].r=0;
        tr[rt].siz=1,tr[rt].rnd=rand();
        tr[rt].val=v;
        return; 
    }
    tr[rt].siz++;
    if(v<=tr[rt].val)
    {
        insert(tr[rt].l,v);
        if(tr[tr[rt].l].rnd<tr[rt].rnd)rturn(rt);
    }else
    {
        insert(tr[rt].r,v);
        if(tr[tr[rt].r].rnd<tr[rt].rnd)lturn(rt);
    }
}
void del(int &rt,int v)
{
    tr[rt].siz--;
    if(tr[rt].val==v)
    {
        if(tr[rt].l==0||tr[rt].r==0){rt=tr[rt].l+tr[rt].r;return;}
        if(tr[tr[rt].l].rnd<tr[tr[rt].r].rnd)
            rturn(rt),del(rt,v);
        else lturn(rt),del(rt,v);
    }else if(v<tr[rt].val)del(tr[rt].l,v);
    else del(tr[rt].r,v);
}
int ask_pre(int rt,int v)
{
    if(!rt)return 0;
    if(v<=tr[rt].val)
        return ask_pre(tr[rt].l,v);
    else
    {
        int ret=ask_pre(tr[rt].r,v);
        return max(tr[rt].val,ret);
    }
}
int ask_sub(int rt,int v)
{
    if(!rt)return INF;
    if(v>=tr[rt].val)
        return ask_sub(tr[rt].r,v);
    else
    {
        int ret=ask_sub(tr[rt].l,v);
        return min(tr[rt].val,ret);
    }
}
int main()
{
    scanf("%d",&n);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(!cnt)
        {
            if(x)cnt--,insert(root,y);
            else cnt++,insert(root,y);
        }else if(cnt>0)
        {
            if(x)
            {
                cnt--;
                int tmp1=ask_pre(root,y),tmp2=ask_sub(root,y);
                if(!tmp1){ans=(ans+abs(tmp2-y))%mod,del(root,tmp2);continue;}
                if(tmp2==INF){ans=(ans+abs(tmp1-y))%mod,del(root,tmp1);continue;}
                if(y-tmp1<=tmp2-y)
                {
                    ans=(ans+abs(y-tmp1))%mod;
                    del(root,tmp1);
                }else
                {
                    ans=(ans+abs(tmp2-y))%mod;
                    del(root,tmp2);
                }
            }else cnt++,insert(root,y);
        }else
        {
            if(x)cnt--,insert(root,y);
            else
            {
                cnt++;
                int tmp1=ask_pre(root,y),tmp2=ask_sub(root,y);
                if(!tmp1){ans=(ans+abs(tmp2-y))%mod,del(root,tmp2);continue;}
                if(tmp2==INF){ans=(ans+abs(tmp1-y))%mod,del(root,tmp1);continue;}
                if(y-tmp1<=tmp2-y)
                {
                    ans=(ans+abs(y-tmp1))%mod;
                    del(root,tmp1);
                }else
                {
                    ans=(ans+abs(tmp2-y))%mod;
                    del(root,tmp2);
                }   
            }
        }
    }
    printf("%d
",ans);
}