【平衡树】宠物收养所

平衡树

传送门：CodeVS1285

思路：用平衡树维护一下每个节点前驱和后继，然后记录一下是宠物还是收养者，没了。

代码如下（用set可以过，此处当做splay练习）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100000
#define INF 0x3f3f3f3f
#define mo 1000000
int n,x,y,root,tot,ans,data[N],val[N],fa[N],op[N],size[N],son[N][2];
int getint(){
	char ch; int sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
void rotate(int x,int w){
	int y=fa[x];
	son[y][w^1]=son[x][w]; if (son[x][w]) fa[son[x][w]]=y;
	fa[x]=fa[y]; if (fa[y]){if (y==son[fa[y]][0]) son[fa[y]][0]=x; else son[fa[y]][1]=x;}
	fa[y]=x; son[x][w]=y;
}
void splay(int x){
	while (fa[x]){
		int y=fa[x];
		if (!fa[y]){if (x==son[y][0]) rotate(x,1); else rotate(x,0);}
		else{
			if (x==son[y][0]){
				if (y==son[fa[y]][0]){rotate(y,1); rotate(x,1);}
				else{rotate(x,1); rotate(x,0);}
			}
			else{
				if (y==son[fa[y]][0]){rotate(x,0); rotate(x,1);}
				else{rotate(y,0); rotate(x,0);}
			}
		}
	}
	root=x;
}
int search(int x,int k){
	while (k!=data[x]){
		if (k<data[x]){if (!son[x][0]) return x; x=son[x][0];}
		else{if (!son[x][1]) return x; x=son[x][1];}
	}
	return x;
}
void ins(int x,int y){
	if (root==0){root=++tot; data[tot]=x; op[tot]=y; fa[tot]=0; size[tot]=1; val[tot]=1; return;}
	int k=search(root,x),kk; bool flag;
	if (x==data[k]){val[k]++; kk=k; flag=1;}
	else{
		data[++tot]=x; op[tot]=y; fa[tot]=k; size[tot]=1; val[tot]=1; flag=0;
		if (x<data[k]) son[k][0]=tot; else son[k][1]=tot;
	}
	while (k){size[k]++; k=fa[k];}
	if (flag) splay(kk); else splay(tot);
}
void del(int x){
	splay(x);
	if (val[x]>1){val[x]--; return;}
	if (!son[x][0]){root=son[x][1]; fa[son[x][1]]=0; return;}
	root=son[x][0]; fa[root]=0;
	int k=search(root,INF);
	splay(k); son[root][1]=son[x][1]; fa[son[x][1]]=root;
}
int query(int x,int k){
	int Min=abs(data[x]-k),ID=x;
	while (k!=data[x]){
		if (abs(data[x]-k)<Min || (abs(data[x]-k)==Min && data[x]<k)){Min=abs(data[x]-k); ID=x;}
		if (k<data[x]){if (!son[x][0]) break; x=son[x][0];}
		else{if (!son[x][1]) break; x=son[x][1];}
	}
	splay(ID); del(ID);
	return Min;
}
	
int main(){
	n=getint();
	for (int i=1;i<=n;i++){
		x=getint(); y=getint();
		if (!root || op[root]==x) ins(y,x);
		else ans=(ans+query(root,y))%mo;
	}
	printf("%d\n",ans%mo);
	
	return 0;
}