题解 P2073 【送花】
Ireliaღ
2019-01-31 21:52:53
## 看到没人写指针版FHQTreap，我来写一发
~~***debug的时候，指针版数据结构直接添加查看这个指针就把指针所指结构体的所有变量全都显示出来了，为什么没多少人用啊。。***~~
### 前置知识：无旋Treap，可以看我[博客](https://www.cnblogs.com/Juruo1103/p/10281403.html)
### 题目要求：资瓷插入节点，删除最值
维护一棵$FHQTreap$，并存储$w$和$c$的总值
#### 插入节点：
先在这棵树查找$c$，如果有直接返回，取消插入（划重点）
然后就可以正常像$FHQTreap$一样查排名分裂合并了，注意更新$total$值
#### 删除最值：
注意判空根，注意更新$total$值，正常分裂出一个节点删除即可
### 最后放出完整代码
```cpp
// luogu-judger-enable-o2
#include <stdio.h>
int Rand() {
static int seed = 2333333;
return seed = (((seed | 66666) + 19260817ll) * 1433223ll) % 0x7f7f7f7f;
}
namespace FHQ{
int totw = 0, totc = 0;
struct Node{
int w, c, size, key;
Node *child[2];
Node(int w, int c):w(w), c(c), size(1), key(Rand()) {child[0] = child[1] = NULL;}
};
Node *root = NULL;
void Update(Node *now) {
now->size = 1;
now->size += now->child[0] ? now->child[0]->size : 0;
now->size += now->child[1] ? now->child[1]->size : 0;
}
void Split(Node *now, int k, Node *&t1, Node *&t2) {
if (!now) {
t1 = t2 = NULL; return;
}
if (k == 0) {
t1 = NULL; t2 = now; return;
}
if (k >= now->size) {
t1 = now; t2 = NULL; return;
}
int ls = now->child[0] ? now->child[0]->size : 0;
if (k <= ls) {
Node *temp;
Split(now->child[0], k, t1, temp);
t2 = now; t2->child[0] = temp; Update(t2); return;
} else {
Node *temp;
Split(now->child[1], k - ls - 1, temp, t2);
t1 = now; t1->child[1] = temp; Update(t1); return;
}
}
Node *Merge(Node *a, Node *b) {
if (!a || !b) return a ? a : b;
if (b->key > a->key) {
a->child[1] = Merge(a->child[1], b);
Update(a); return a;
} else {
b->child[0] = Merge(a, b->child[0]);
Update(b); return b;
}
}
int Rank(Node *now, int k) {
if (!now) return 1;
int ls = now->child[0] ? now->child[0]->size : 0;
if (k < now->c) return Rank(now->child[0], k);
else if (k > now->c) return Rank(now->child[1], k) + ls + 1;
else return ls + 1;
}
bool Insert(int w, int c) {
if (!root) {
root = new Node(w, c);
totw += w; totc += c;
return true;
}
if (root) {
Node *now = root;
while (now) {
if (c < now->c) now = now->child[0];
else if (c > now->c) now = now->child[1];
else return false;
}
}
Node *temp = new Node(w, c);
int rank = Rank(root, c);
Node *lt, *rt;
Split(root, rank - 1, lt, rt);
root = Merge(lt, Merge(temp, rt));
totw += w; totc += c;
return true;
}
void DelMax() {
if (!root) return;
Node *lt, *rt;
Split(root, root->size - 1, lt, rt);
root = lt; totw -= rt->w; totc -= rt->c;
delete rt; return;
}
void DelMin() {
if (!root) return;
Node *lt, *rt;
Split(root, 1, lt, rt);
root = rt; totw -= lt->w; totc -= lt->c;
delete lt; return;
}
}
int main() {
int opt = 0, w, c;
while (scanf("%d", &opt), opt != -1) {
switch(opt) {
case 1: {
scanf("%d %d", &w, &c);
FHQ::Insert(w, c);
break;
}
case 2: {
FHQ::DelMax();
break;
}
case 3: {
FHQ::DelMin();
break;
}
}
}
printf("%d %d\n", FHQ::totw, FHQ::totc);
return 0;
}
/*
1 1 1
1 2 5
2
1 3 3
3
1 5 2
-1
*/
```
输入$opt$那里压了一下行，因为$while$里有逗号是返回最后一句的$true/false$