BZOJ [HNOI2004]宠物收养所 （Splay）
思路：
开始想的是建立两棵Splay， 来回倒，宠物建立一个， 人建立一个， 然后剩下的问题就是找另一个树的前驱和后继。
但是在超时， 可能哪里写挫了， 也可能是两棵本身就过不了。
于是借鉴了另一个很机智的思路：
想一想就知道， 在任意时刻，不可能既有宠物，又有人。
因此我们建立一个Splay 即可， 开一个变量 标记当前时刻 树里存的是人 还是宠物。
这样就转换成了一棵树上的求前驱和后继。
因一个傻逼错误， wa，tle 了n 遍， （还是水啊， 每次写Splay 都会挫！）
其实还是挺水的， 这个题代码就不要参考了吧（太长太丑）， 懂思路就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 80000 + 10;
const int mod = 1000000;
int ch[maxn][2];
int cnt[maxn];
int pre[maxn];
int root;
int ss[maxn];
int top;
int val[maxn];
int tot;
int id2;
void pushup(int r){
if (!r) return;
int lson = ch[r][0];
int rson = ch[r][1];
cnt[r] = 1;
if (lson) cnt[r] += cnt[lson];
if (rson) cnt[r] += cnt[rson];
}
void pushdown(int r){}
void Rotate(int x,int kind){
if (!x) return;
int y = pre[x];
pushdown(y); pushdown(x);
ch[y][!kind] = ch[x][kind];
pre[ch[x][kind] ] = y;
if (pre[y]){
int p = ch[pre[y] ][1] == y;
ch[pre[y] ][p] = x;
}
pre[x] = pre[y];
ch[x][kind] = y;
pre[y] = x;
pushup(y);
}
void Splay(int x,int f){
if (!x) return;
pushdown(x);
while(pre[x] != f){
pushdown(pre[pre[x] ]);
pushdown(pre[x]);
pushdown(x);
if (pre[pre[x] ] == f){
int kind = ch[pre[x] ][0] == x;
Rotate(x, kind);
}
else {
int y = pre[x];
int kind = ch[pre[y] ][0] == y;
if (ch[y][kind] == x){
Rotate(x, !kind);
Rotate(x, kind);
}
else {
Rotate(y, kind);
Rotate(x, kind);
}
}
}
pushup(x);
if (f == 0) root = x;
}
void newnode(int& r,int f,int x){
if (top >= 1){
r = ss[top];
--top;
}
else {
r = ++tot;
}
pre[r] = f;
cnt[r] = 1;
val[r] = x;
ch[r][0] = ch[r][1] = 0;
}
bool insert(int x){
if (root == 0){
newnode(root, 0, x);
}
else {
int cur = root;
while(ch[cur ][val[cur] < x ]){
pushdown(cur);
if (val[cur] == x){
Splay(cur, 0);
return false;
}
cur = ch[cur][val[cur] < x ];
}
newnode(ch[cur][val[cur] < x], cur, x);
Splay(ch[cur][val[cur] < x], 0);
pushup(cur);
return true;
}
}
void Select(int x,int f){
if (!x) return;
int cur = root;
while(1){
pushdown(cur);
if (cnt[ch[cur][0] ] + 1 == x){
break;
}
else if (cnt[ch[cur][0] ] >= x){
cur = ch[cur][0];
}
else {
x -= (cnt[ch[cur][0] ] + 1);
cur = ch[cur][1];
}
}
Splay(cur, 0);
pushup(cur);
}
void clear(int x){
cnt[x] = 0;
ch[x][0] = ch[x][1] = 0;
pre[x] = 0;
val[x] = 0;
}
void del(int x){
if (!x) return;
Splay(x, 0);
if (ch[x][1]){
int t = root;
root = ch[root][1];
Select(1, 0);
ch[root][0] = ch[t][0];
if (ch[root][0]){
pre[ch[root][0] ] = root;
}
}
else root = ch[root][0];
pre[root] = 0;
clear(x);
ss[++top] = x;
pushup(root);
}
void init(){
top = tot = root = 0;
}
void dfs(int cur){
if (cur == 0) return;
dfs(ch[cur][0]);
printf("node: %d, lson : %d, rson: %d, cnt = %d,val = %dn", cur, ch[cur][0], ch[cur][1], cnt[cur], val[cur]);
dfs(ch[cur][1]);
}
void debug(){
printf("root : %dn", root);
dfs(root);
}
int get_pre(int x){
if (!x) return 0;
x = ch[x][0];
if (!x) return 0;
while(ch[x][1]) x = ch[x][1];
return x;
}
int get_next(int x){
if (!x) return 0;
x = ch[x][1];
if (!x) return 0;
while(ch[x][0])x = ch[x][0];
return x;
}
int aaa(int x){
if (x < 0) return -x;
return x;
}
void add(long long& ans, int x){
ans += x;
if(ans >= mod) ans %= mod;
}
int main(){
int n;
scanf("%d",&n);
long long ans = 0;
int sum0 = 0;
for (int i = 0; i < n; ++i){
int id, x;
scanf("%d %d",&id, &x);
if (id == 0 && sum0 >= 0){
insert(x);
sum0++;
continue;
}
if (id == 1 && sum0 <= 0) {
insert(x);
sum0--;
continue;
}
bool ok = insert(x);
int pos = root;
if (!ok){
if (id == 1) sum0--;
else sum0++;
}
else {
int pre_ = get_pre(root);
int ans1 = -1;
if (pre_) ans1 = aaa(val[pre_]-x);
int next_ = get_next(root);
int ans2 = -1;
if (next_) ans2 = aaa(val[next_]-x);
if (ans1 != -1 && ans2 != -1){
if (ans2 < ans1){
add(ans, ans2);
del(next_);
}
else {
add(ans, ans1);
del(pre_);
}
}
else if (ans1 != -1){
add(ans, ans1);
del(pre_);
}
else if (ans2 != -1){
add(ans, ans2);
del(next_);
}
else {
}
if (id == 1) sum0--;
else sum0++;
}
del(pos);
}
printf("%lldn", ans);
return 0;
}
1208: [HNOI2004]宠物收养所
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 9010 Solved: 3610
[ Submit][ Status][ Discuss]
Description
最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。 1． 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。 2． 收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。 一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。【任务描述】你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。
Input
第一行为一个正整数n，n<=80000，表示一年当中来到收养所的宠物和领养者的总数。接下来的n行，按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数a, b，其中a=0表示宠物，a=1表示领养者，b表示宠物的特点值或是领养者希望领养宠物的特点值。（同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过10000个）
Output
仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。
Sample Input
5
0 2
0 4
1 3
1 2
1 5
Sample Output
3
(abs(3-2) + abs(2-4)=3，最后一个领养者没有宠物可以领养)
HINT
Source
[ Submit][ Status][ Discuss]相关知识
P2286 [HNOI2004]宠物收养场
[BZOJ1208]宠物收养所（Splay）
【HNOI2004】宠物收养所
[HNOI2004]宠物收养所
宠物收养所
P2286 [HNOI2004] 宠物收养场
[HNOI2004]宠物收养场 题解 set
宠物收养所(宠物收养所在哪里)
东莞宠物收养所
宠物收养所题解
网址: BZOJ [HNOI2004]宠物收养所 （Splay） https://m.mcbbbk.com/newsview738261.html
| 上一篇: 上海杨浦区宠物医院 |
下一篇: 重庆宠物领养中心地址在哪里 重庆 |
