题解 P2343 【宝石管理系统】
Ireliaღ
2019-04-24 17:48:27
**本题第一篇替罪羊树题解**
题解里以Splay和Treap为主。但是如果只做权值树,感觉替罪羊树码量最小,跑的还最快。~~毕竟暴力出奇迹~~
## 题目大意
给一组数据和两种操作,分别为插入一个数和查询**第$k$大**
## 解法
- 使用替罪羊树维护,注意**数据是从大到小排的**
- 对于给出的数据,**降序**排序后二分建树~~如果懒的话一个一个insert也问题不大,多个$log$无伤大雅~~
- 对于两种操作,平衡树板子
## 代码
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
const int MAXN = 1e5 + 5;
const double A = 0.8;
int a[MAXN];
struct Node{
int val, siz;
Node *ch[2];
Node(int val): val(val) {
siz = 1;
ch[0] = ch[1] = NULL;
}
void Update() {
siz = (ch[0] ? ch[0]->siz : 0) + (ch[1] ? ch[1]->siz : 0) + 1;
}
bool Bad() {
int ls = ch[0] ? ch[0]->siz : 0, rs = ch[1] ? ch[1]->siz : 0;
return (double)ls > (double)siz * A || (double)rs > (double)siz * A;
}
};
Node *rt = NULL;
vector<Node*> vec;
void Build(Node *&now, int l, int r) {
if (l > r) return;
int mid = l + r >> 1;
now = new Node(a[mid]);
Build(now->ch[0], l, mid - 1);
Build(now->ch[1], mid + 1, r);
now->Update();
}
void Dfs(Node *now) {
if (!now) return;
Dfs(now->ch[0]);
Node *tmp = now->ch[1];
now->ch[0] = now->ch[1] = NULL;
now->siz = 1;
vec.push_back(now);
Dfs(tmp);
}
void Rebuild(Node *&now, int l, int r) {
if (l > r) return;
int mid = l + r >> 1;
now = vec[mid];
Rebuild(now->ch[0], l, mid - 1);
Rebuild(now->ch[1], mid + 1, r);
now->Update();
}
void Insert(Node *&now, int val) {
if (now == NULL) {
now = new Node(val);
return;
} else {
Insert(val > now->val ? now->ch[0] : now->ch[1], val);
now->Update();
if (now->Bad()) {
vec.clear();
Dfs(now);
int tot = vec.size();
Rebuild(now, 0, tot - 1);
}
}
}
/*
int Kth(Node *now, int k) {
if (!now) return 0;
int ls = now->ch[0] ? now->ch[0]->siz : 0;
if (k <= ls) return Kth(now->ch[0], k);
else if (k == ls + 1) return now->val;
else return Kth(now->ch[1], k - ls - 1);
}
*/
int Kth(int rank) {
if (!rt) return 1;
Node *now = rt, *prev = NULL;
while (now) {
prev = now;
int ls = now->ch[0] ? now->ch[0]->siz : 0;
if (rank <= ls) now = now->ch[0];
else if (rank <= ls + 1) break;
else rank -= ls + 1, now = now->ch[1];
}
return prev->val;
}
int cmp(const void *a, const void *b) {
return *(int*)b - *(int*)a;
}
int main() {
ios :: sync_with_stdio(false); cin.tie(NULL);
int m, q;
cin >> m >> q;
for (int i = 1; i <= m; i++) cin >> a[i];
qsort(a + 1, m, sizeof(int), cmp);
Build(rt, 1, m);
for (int i = 1; i <= q; i++) {
int op, x;
cin >> op >> x;
if (op == 1)
cout << Kth(x) << endl;
else
Insert(rt, x);
}
return 0;
}
```