【题解】 [HNOI2004]宠物收养场（Splay）

Solution:

\(Splay\)板子，注意交换的地方，然后就是注意不要越界node[x]，应该是\(node[now]\)，其次就是数组可以开大点
Code:

//It is coded by Ning_Mew on 4.10

#include<bits/stdc++.h>

#define ls(x) node[x].ch[0]

#define rs(x) node[x].ch[1]

#define fa(x) node[x].fa

#define root node[0].ch[1]

using namespace std;

const int maxn=200000+10,INF=1e9+7,MOD=1e6;

int n,ans=0,tot=0;

struct Node {

	int fa,ch[2],cnt,val,size;

} node[maxn];

void update(int x) {node[x].size=node[ls(x)].size+node[rs(x)].size+node[x].cnt;}

void connect(int x,int fa,int how) {node[x].fa=fa;node[fa].ch[how]=x;}

int ident(int x) {return x==node[fa(x)].ch[0]?0:1;}

void rorate(int x) {

	int Y=fa(x),R=fa(Y);	int Yson=ident(x),Rson=ident(Y);

	connect(node[x].ch[Yson^1],Y,Yson);

	connect(Y,x,Yson^1);

	connect(x,R,Rson);

	update(Y);update(x);

}

void Splay(int x,int goal) {

	int to=fa(goal);

	while(fa(x)!=to) {

		if(fa(fa(x))==to)rorate(x);

		else if(ident(x)==ident(fa(x)))rorate(fa(x)),rorate(x);

		else rorate(x),rorate(x);

	}

}

int newnode(int x,int fa) {node[++tot].val=x;node[tot].cnt=node[tot].size=1;node[tot].fa=fa;return tot;}

void ins(int x) {

	int now=root;

	if(!root) {newnode(x,0);root=tot;return;

	} else {

		while(1) {

			node[now].size++;

			if(node[now].val==x) {node[now].cnt++;Splay(now,root);return;}

			int nxt=x<node[now].val?0:1;

			if(!node[now].ch[nxt]) {

				int p=newnode(x,now);

				node[now].ch[nxt]=p; Splay(p,root);

				return;

			}

			now=node[now].ch[nxt];

		}

	}

}

int find(int x) {

	int now=root;

	while(1) {

		if(!now)return 0;

		if(node[now].val==x) {Splay(now,root);return now;}

		int nxt=x<node[now].val?0:1;

		now=node[now].ch[nxt];

	}

}

void del(int x) {

	int pos=find(x);

	if(!pos)return;

	if(node[pos].cnt>1) {node[pos].cnt--;node[pos].size--;return;}

	if(!node[pos].ch[0]&&!node[pos].ch[1]) {root=0;return;}

	if(!node[pos].ch[0]) {root=node[pos].ch[1];node[root].fa=0;return;

	} else {

		int left=ls(pos);///

		while(rs(left))left=rs(left);

		Splay(left,node[pos].ch[0]);

		connect(node[pos].ch[1],left,1);

		connect(left,0,1);

		update(left);return;

	}

}

int lower(int x) {

	int now=root,ans=-INF;

	while(now) {

		if(node[now].val<=x)ans=max(ans,node[now].val);

		int nxt=x<=node[now].val?0:1;

		now=node[now].ch[nxt];

	}

	return ans;

}

int upper(int x) {

	int now=root,ans=INF;

	while(now) {

		if(node[now].val>=x)ans=min(ans,node[now].val);

		int nxt=x<node[now].val?0:1;

		now=node[now].ch[nxt];

	}

	return ans;

}

int num[5];

int main() {

	scanf("%d",&n);

	int x,opt,stat=0;

	for(int i=1; i<=n; i++) {

		scanf("%d%d",&opt,&x);

		if(num[stat]==0) {

			ins(x);

			num[opt]++;

			stat=opt;/*cout<<"ins finished"<<endl;*/

		} else {

			if(opt==stat)ins(x),num[opt]++/*,cout<<"ins finished"<<endl*/;

			else {

				num[stat]--;

				int up=upper(x),low=lower(x),box=INF;

				if(up!=INF)box=min(box,abs(x-up));

				if(low!=-INF)box=min(box,abs(x-low));

				//cout<<up<<' '<<low<<' '<<box<<endl;

				ans=(ans+box)%MOD;

				if(box==abs(x-low))del(low);

				else del(up);

				//cout<<"del finished"<<endl;

			}

		}

		//cout<<"--"<<stat<<endl;

	}

	printf("%d\n",ans);

	return 0;

}
巴特西

【题解】 [HNOI2004]宠物收养场（Splay）

Solution:

Code:

最新文章

热门文章
