# Irelia

### 题解 P2343 【宝石管理系统】

posted on 2019-04-24 17:48:27 | under 题解 |

## 解法

• 使用替罪羊树维护，注意数据是从大到小排的

• 对于给出的数据，降序排序后二分建树如果懒的话一个一个insert也问题不大，多个 $log$ 无伤大雅

• 对于两种操作，平衡树板子

## 代码

// 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;
}

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();
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;
}