[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\n",ans);

	return 0;

}
巴特西

[HNOI2004]宠物收养场

最新文章

热门文章
