题目链接
[HNOI2004]宠物收养所
题解
这基本上就是一个裸的treap，听说set可以秒此题，但是本着练习treap的思想我还是手打了一份平衡树。首先人和宠物是一样的，只需要判断一下现在收养所里面装的是什么，来东西了，一样就直接insert，不一样就找一下前驱后继判一下选哪个然后把那个remove了，每次判一下树是否为空，空了就换成当前来的东西的类型。应该比较简单codevs上都是钻石（我猜是因为set可以做就很简单了）
代码
我是拿的板子所以多写了rank和kth
#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
struct Node{int v,r,s;Node *ch[2];Node(int v):v(v){r=rand();s=1;ch[0]=ch[1]=NULL;}int cmp(int x){if(v==x) return -1;return v>x?0:1;}void maintain(){s=1;if(ch[0]!=NULL) s+=ch[0]->s;if(ch[1]!=NULL) s+=ch[1]->s;}
};void rotate(Node* &p,int c)
{Node *t=p->ch[c^1];p->ch[c^1]=t->ch[c];t->ch[c]=p;p->maintain();t->maintain();p=t;return ;
}void insert(Node* &p,int x)
{if(p==NULL){p=new Node(x);return ;}int tcmp=p->cmp(x);//int tcmpa=(x>p->v ? 1:0) 有重复的时候用这一句 insert(p->ch[tcmp],x);if(p->ch[tcmp]->r > p->r) rotate(p,tcmp^1);p->maintain();
}void remove(Node* &p,const int x)
{int tcmp=p->cmp(x); if(tcmp==-1){if(p->ch[0]==NULL) p=p->ch[1];//**remove(p->ch[1],x)else if(p->ch[1]==NULL) p=p->ch[0];//**remove(p->ch[0],x)else{int tmp=(p->ch[0]->r > p->ch[1]->r ? 1:0);rotate(p,tmp);remove(p->ch[tmp],x);//**p=p->ch[tmp];}}else remove(p->ch[tcmp],x);if(p!=NULL) p->maintain();//** 漏了一句 return ;
}bool find(Node* p,const int x)
{while(p!=NULL){int tcmp=p->cmp(x);if(tcmp==-1) return true;p=p->ch[tcmp];}return false;
}int kth(Node* p,int x)
{if(p==NULL||x<0||x>p->s)return -1;int d=(p->ch[1]==NULL?0:p->ch[1]->s);if(x==d+1) return p->v;if(x<=d) return kth(p->ch[1],x);return kth(p->ch[0],x-d-1);
} int rank(Node* p,const int x)
{int ret=1;while(p!=NULL){int tcmp=p->cmp(x),d=(p->ch[1]==NULL?0:p->ch[1]->s);if(tcmp==-1) return ret+d;if(tcmp==0) ret=ret+1+d;else ret++;p=p->ch[tcmp];}return ret;
}int pre(Node* p,const int x)
{int ret=0;while(p!=NULL){int tcmp=p->cmp(x);if(tcmp==-1) return x;if(tcmp) ret=max(ret,p->v);p=p->ch[tcmp];}return ret;
}const int INF=(1<<30);
int last(Node* p,const int x)
{int ret=INF;while(p!=NULL){int tcmp=p->cmp(x);if(tcmp==-1) return x;if(!tcmp) ret=min(ret,p->v);p=p->ch[tcmp];}return ret;
}inline int read()
{int ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';return ret;
}const int MOD=1000000;
int main()
{srand(0);Node *root=NULL;int kind,n,sum=0;cin>>n;for(int i=1,ins,x;i<=n;i++){ins=read();x=read();if(root==NULL) kind=ins,insert(root,x);else if(ins==kind) insert(root,x);else{int PRE=pre(root,x);int LAST=last(root,x);int d=INF,wh;if(PRE&&abs(PRE-x)<d) d=abs(PRE-x),wh=PRE;if(LAST!=INF&&abs(LAST-x)<d) d=abs(LAST-x),wh=LAST;sum=(sum+d)%MOD;remove(root,wh);}}cout<<sum;return 0;
}