[HNOI2004]宠物收养场

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
",ans);
	return 0;
}