题解 P1801 【黑匣子_NOI导刊2010提高（06）】
Ireliaღ
2019-01-30 22:10:18
## 我看这么多题解没有人写指针版的无旋Treap，我来写一个
*如果不会FHQTreap可以看我的[博客](https://www.cnblogs.com/Juruo1103/p/10281403.html)*
**指针版FHQ又好写又好调跑的还快，墙裂推荐**
题面无需多讲，插入数值和查询第$k$小，平衡树模板操作
无旋$Treap$由于有按照$size$来$Split$的功能，所以我们可以按照二叉搜索树的性质写一个$Rank$函数，然后这两种操作都可以基于$Rank$完成
#### 插入数值
查$Rank$，分裂出$size$为$Rank - 1$的子树，把新节点放入中间合并，代码如下
```cpp
void Insert(int val) {
int rank = Rank(root, val);
Node *temp1, *temp2;
Split(root, rank, temp1, temp2);
Node *nod = new Node(val);
root = Merge(temp1, nod);
root = Merge(root, temp2);
}
```
#### 查询第k小
按照需要的$k$值分裂出$size$为$k - 1$的子树，在剩余部分分裂出$size$为$1$的节点，输出节点权值，然后原样拼回去，代码如下
```cpp
int FindKth(int k) {
Node *x1, *x2, *y1, *y2;
Split(root, k - 1, x1, x2);
Split(x2, 1, y1, y2);
Node *now = y1;
root = Merge(x1, Merge(now, y2));
return now ? now->val : 0;
}
```
### 完整代码
```cpp
#include <cstdio>
#include <algorithm>
using std::min;
using std::max;
const int MAXM = 2e5 + 5;
int add[MAXM], get[MAXM];
int n, m;
int Rand() {
static int seed = 39444;
return seed = (((seed ^ 1433223) + 810872ll) * 19260817ll) % 2147483647;
}
struct Node{
Node *child[2];
int val, key, size;
Node(int val):val(val), size(1), key(Rand()) {
child[0] = NULL; child[1] = NULL;
}
void Update() {
size = 1;
if (child[0]) size += child[0]->size;
if (child[1]) size += child[1]->size;
}
};
Node *root = NULL;
Node* Merge(Node* a, Node* b) {
if (!a || !b) return a ? a : b;
if (a->key < b->key) {
a->child[1] = Merge(a->child[1], b);
a->Update();
return a;
} else {
b->child[0] = Merge(a, b->child[0]);
b->Update();
return b;
}
}
void Split(Node *now, int k, Node *&t1, Node *&t2) {
if (!now) {
t1 = t2 = NULL; return;
}
if (!k) {
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 (ls >= k) {
Node *temp;
Split(now->child[0], k, t1, temp);
t2 = now; t2->child[0] = temp;
t2->Update(); return;
} else {
Node *temp;
Split(now->child[1], k - ls - 1, temp, t2);
t1 = now; t1->child[1] = temp;
t1->Update(); return;
}
}
int Rank(Node *now, int k) {
if (!now) return 0;
int ls = now->child[0] ? now->child[0]->size : 0;
if (now->val <= k) return ls + 1 + Rank(now->child[1], k);
else return Rank(now->child[0], k);
}
int FindKth(int k) {
Node *x1, *x2, *y1, *y2;
Split(root, k - 1, x1, x2);
Split(x2, 1, y1, y2);
Node *now = y1;
root = Merge(x1, Merge(now, y2));
return now ? now->val : 0;
}
void Insert(int val) {
int rank = Rank(root, val);
Node *temp1, *temp2;
Split(root, rank, temp1, temp2);
Node *nod = new Node(val);
root = Merge(temp1, nod);
root = Merge(root, temp2);
}
int main() {
scanf("%d %d", &m, &n);
for (int i = 1; i <= m; i++) {
scanf("%d", add + i);
}
int ii = 0, cur = 1;
for (int i = 1; i <= n; i++) {
scanf("%d", get + i);
while (cur <= get[i]) {
Insert(add[cur]); cur++;
}
printf("%d\n", FindKth(++ii));
}
return 0;
}
```