题目描述

宠物收养所

普通平衡树的常数大一点

算法1

(普通平衡树) $O(nlogn)$

#include<bits/stdc++.h>
using namespace std;

const int N=100010,INF=1e8,mod=1e6;
int n;
struct node
{
    int l,r;
    int key,val;
    int cnt,size;
}tr[N];

int root,idx;

void pushup(int p)
{
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
int get_node(int key)
{
    tr[++idx].key=key;
    tr[idx].val=rand();
    tr[idx].size=tr[idx].cnt=1;
    return idx;
}
void zig(int &p)
{
    int q=tr[p].l;
    tr[p].l=tr[q].r;
    tr[q].r=p;
    p=q;
    pushup(tr[p].r),pushup(p);
}
void zag(int &p)
{
    int q=tr[p].r;
    tr[p].r=tr[q].l;
    tr[q].l=p;
    p=q;
    pushup(tr[p].l),pushup(p);
}
void  build()
{
    get_node(-INF),get_node(INF);
    root=1,tr[1].r=2;
    if(tr[1].val<tr[2].val) zag(root);
    pushup(root);
}
void insert(int &p,int key)
{
    if(!p)  p=get_node(key);
    else if(tr[p].key==key) tr[p].cnt++;
    else if(tr[p].key>key)
    {
        insert(tr[p].l,key);
        if(tr[tr[p].l].val>tr[p].val)   zig(p);
    }
    else
    {
        insert(tr[p].r,key);
        if(tr[tr[p].r].val>tr[p].val)   zag(p);
    }
    pushup(p);
}
void remove(int &p,int key)
{
    if(!p)  return;
    else if(tr[p].key==key)
    {
        if(tr[p].cnt>1) tr[p].cnt--;
        else if(tr[p].l||tr[p].r)
        {
            if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)  
            {
                zig(p);
                remove(tr[p].r,key);
            }
            else
            {
                zag(p);
                remove(tr[p].l,key);
            }

        }
        else p=0;
    }
    else if(tr[p].key>key)  remove(tr[p].l,key);
    else remove(tr[p].r,key);
    pushup(p);
}

int get_rank_by_key(int p,int key)
{
    if(!p)  return 0;
    if(tr[p].key==key)  return tr[tr[p].l].size+1;
    else if(tr[p].key>key)  return get_rank_by_key(tr[p].l,key);
    return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank)
{
    if(!p)  return INF;
    else if(tr[tr[p].l].size>=rank) return get_key_by_rank(tr[p].l,rank);
    else if(tr[tr[p].l].size+tr[p].cnt>=rank)   return tr[p].key;
    return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
int get_prev(int p,int key)
{
    if(!p)  return -INF;
    if(tr[p].key>=key)  return get_prev(tr[p].l,key);
    return max(tr[p].key,get_prev(tr[p].r,key));
}

int get_next(int p,int key)
{
    if(!p)  return INF;
    if(tr[p].key<=key)  return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));
}

int main()
{
    int flag=0,res=0;
    scanf("%d",&n);
    build();
    int op,x;
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&op,&x);
        if(flag==op||tr[root].size==2)
        {
            flag=op;
            insert(root,x);
        }
        else
        {
            int a=get_prev(root,x),b=get_next(root,x);
            if(a==-INF && b==INF) continue;
            if(a==-INF or b!=INF and abs(a-x)>abs(b-x)) a=b;
            res=(res+abs(a-x))%mod;
            remove(root,a);
        }
    }
    printf("%d\n",res);

    return 0;
}

算法2

(FHQ平衡树) $O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
const int N =100010,mod=1e6;

struct node
{
    int l,r;
    int val,key,size;//索引,值,大小
}tr[N];

int root,idx;

int get_node(int key)
{
    int u=++idx;
    tr[u].key=key;
    tr[u].val=rand();
    tr[u].size=1;
    return u;
}
void pushup(int u)
{
    tr[u].size=tr[tr[u].l].size+tr[tr[u].r].size+1;
}
void split(int u,int key,int &x,int &y)
{
    if(!u)  x=y=0;//访问到了空节点,这时的左右子树都是0
    else
    {
        if(tr[u].key<=key)//当前节点的值大于给定的值
        {
            x=u;//u和它的左节点一定在x里
            split(tr[u].r,key,tr[u].r,y);//分裂u右节点到y里
        }
        else 
        {
            y=u;//u和它的右节点一定在y里
            split(tr[u].l,key,x,tr[u].l);//分裂u左节点到x里
        }
        pushup(u);//更新
    }
}
int merge(int x,int y)
{
    if(!x||!y)  return x+y;//x为0,返回y！y为0,返回x!
    if(tr[x].val>tr[y].val)
    {//右上方
        tr[x].r=merge(tr[x].r,y);
        pushup(x);
        return x;
    }
    else
    {//左下方
        tr[y].l=merge(x,tr[y].l);
        pushup(y);
        return y;
    }
}
int x,y,z;
void ins(int key)
{
    split(root,key,x,y);
    root=merge(merge(x,get_node(key)),y);
}
void dele(int key)
{
    split(root,key,x,y);
    split(x,key-1,x,z);
    z=merge(tr[z].l,tr[z].r);
    root=merge(merge(x,z),y);
}
int get_prev(int key)
{
    split(root,key-1,x,y);
    int u=x,res=-1;
    while(tr[u].r)  u=tr[u].r;
    if(x)   res=tr[u].key;
    root=merge(x,y);
    return res;
}
int get_next(int key)
{
    split(root,key,x,y);
    int u=y,res=-1;
    while(tr[u].l)    u=tr[u].l;
    if(y)   res=tr[u].key;
    root=merge(x,y);
    return res;
}
void dfs(int u)
{
    if(!u)  return;
    dfs(tr[u].l);
    printf("%d ",tr[u].key);
    dfs(tr[u].r);
}
int main()
{
    int n,flag;
    scanf("%d",&n);

    int res=0;
    for(int i=0;i<n;i++)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(!tr[root].size||flag==op)
        {
            flag=op;
            ins(x);
        }
        else
        {
            int a=get_prev(x),b=get_next(x);
            if(a==-1 || b!=-1 && abs(a-x)>abs(b-x))   a=b;
            res=(res+abs(a-x))%mod;
            dele(a);
        }
    }
    printf("%d",res);
}