LuoguP2286「HNOI2004」题解

发表于

Splay的应用

Description

凡凡开了一间宠物收养场。收养场提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。

每个领养者都希望领养到自己满意的宠物，凡凡根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养场总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。

被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。

收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。

一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。

你得到了一年当中，领养者和被收养宠物到来收养所的情况，请你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

Samples

Input #1

1
2
3
4
5
6
5                  
0 2                      
0 4                         
1 3
1 2
1 5

Output #1

1
3

Explanation

abs(3-2) + abs(2-4) = 3
最后一个领养者没有宠物可以领养。

Solution

考虑记录一下当前造成询问的节点时宠物多还是领养者多, 这样我们就可以随时在人和宠物之间转换, 而不用维护两棵splay.

每当加入一个宠物时, 如果是宠物多那么就直接插入, 否则直接查找当前顾客在splay里面的前趋&后继.

然后把他统计进答案, 拉出来Remove掉.

如果来了一个顾客, 做一遍上面操作的反过程即可.

Code

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
/* Headers */
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os - obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 8e4 + 10;
const int mod = 1e6;
const int inf = INT_MAX;
struct Tree{
	int ch[2], fa, cnt, size, val;
	#define Lef(x, k) Splay[Splay[x].ch[0]].k
	#define Rig(x, k) Splay[Splay[x].ch[1]].k
}Splay[MAXN];
int Node, n, root, cnt, ans, k;
/* functions */
inline bool FIND(int x) {
	return (Splay[Splay[x].fa].ch[1] == x);
}
inline void pushUp(int x) {
	Splay[x].size = Lef(x, size) + Rig(x, size) + Splay[x].cnt;
}
inline void Rotate(int x) {
	int fx = Splay[x].fa, fy = Splay[fx].fa;
	int chx = FIND(x), chy = Splay[x].ch[chx ^ 1];
	Splay[fx].ch[chx] = chy; Splay[chy].fa = fx;
	Splay[fy].ch[FIND(fx)] = x; Splay[x].fa = fy;
	Splay[x].ch[chx ^ 1] = fx; Splay[fx].fa = x;
	pushUp(fx); pushUp(x);
}
inline void splay(int x, int rt = 0) {
	while(Splay[x].fa != rt) {
		int fx = Splay[x].fa, fy = Splay[fx].fa;
		if(fy != rt) {
			if(FIND(x) == FIND(fx)) Rotate(fx);
			else Rotate(x);
		}
		Rotate(x);
	}
	if(!rt) root = x;
}
inline void Insert(int x) {
	int rt = root, p = 0;
	while(rt && Splay[rt].val != x) {
		p = rt;
		rt = Splay[rt].ch[x > Splay[rt].val];
	}
	if(rt) Splay[rt].cnt++;
	else {
		rt = ++Node;
		if(p) Splay[p].ch[x > Splay[p].val] = rt;
		Splay[rt].ch[0] = Splay[rt].ch[1] = 0;
		Splay[rt].fa = p; Splay[rt].val = x;
		Splay[rt].size = Splay[rt].cnt = 1;
	}
	splay(rt);
}
inline void LowerX(int x) {
	int rt = root;
	while(Splay[rt].ch[x > Splay[rt].val] && x != Splay[rt].val) 
		rt = Splay[rt].ch[x > Splay[rt].val];
	splay(rt);
}
inline int Querypre(int x) {
	LowerX(x);
	if(Splay[root].val < x) return root;
	int rt = Splay[root].ch[0];
	while(Splay[rt].ch[1]) rt = Splay[rt].ch[1];
	return rt;
}
inline int Querysuf(int x) {
	LowerX(x);
	if(Splay[root].val > x) return root;
	int rt = Splay[root].ch[1];
	while(Splay[rt].ch[0]) rt = Splay[rt].ch[0];
	return rt;
}
inline void Remove(int x) {
	int last = Querypre(x), next = Querysuf(x);
	splay(last); splay(next, last);
	int del = Splay[next].ch[0];
	if(Splay[del].cnt > 1) {Splay[del].cnt--; splay(del);}
	else Splay[next].ch[0] = 0;
}
int main(int argc,char *argv[]){
	scanf("%d", &n);
	Insert(inf), Insert(-inf);
	while(n--) {
		int a, x; scanf("%d %d", &a, &x);
		if(cnt == 0) Insert(x);
		else if(cnt > 0) {
			if(a == 0) Insert(x);
			else {
				int pre = Splay[Querypre(x)].val;
				int nxt = Splay[Querysuf(x)].val;
				if(std::abs(pre - x) <= std::abs(nxt - x)) {
					(ans += (std::abs(pre - x))) %= mod;
					Remove(pre);
				}
				else {
					(ans += (std::abs(nxt - x))) %= mod;
					Remove(nxt);
				}
			}
		}
		else if(cnt < 0) {
			if(a == 1) Insert(x);
			else {
				int pre = Splay[Querypre(x)].val;
				int nxt = Splay[Querysuf(x)].val;
				if(std::abs(pre - x) <= std::abs(nxt - x)) {
					(ans += (std::abs(pre - x))) %= mod;
					Remove(pre);
				}
				else {
					(ans += (std::abs(nxt - x))) %= mod;
					Remove(nxt);
				}
			}
		}
		cnt = cnt + ((a == 0) ? 1 : -1);
	}	
	printf("%d\n", (ans < 0) ? 0 : ans);
	return 0;
}

THE END