题解 P2343 【宝石管理系统】

Ireliaღ

2019-04-24 17:48:27

Solution

**本题第一篇替罪羊树题解** 题解里以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; } ```