题解 P3835 【【模板】可持久化平衡树】
Ireliaღ
2019-06-02 20:31:59
## 不加平衡措施的BST
本来写的替罪羊，过了样例，交上去WA了。我想看看是不是替罪羊重构出了问题，于是把重构删掉了，感觉会T，结果A了。。。
跑的挺快的，用`new`开内存还只跑了5557ms
具体如何可持久化，就是在递归对一个节点进行修改时，先复制当前节点。这样的话，每次进行操作前，直接将当前根先指向历史根，然后跑函数，就不用每次把历史版本传参传下来了。
代码如下
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int MAXN = 5e5 + 5;
//const float Alpha = 0.7;
const int INF = 0x7fffffff;
int n;
struct Node{
int val, cnt, siz, cov;
Node* ch[2];
Node() {}
Node(int val) : val(val) {
siz = cov = cnt = 1;
ch[0] = ch[1] = NULL;
}
};
Node *rt[MAXN];
//vector<Node*> vec;
stack<Node*> stk;
Node *newNode(int val = 0) {
if (stk.empty()) return new Node(val);
Node *p = stk.top(); stk.pop();
*p = Node(val);
return p;
}
Node *Copy(Node *now) {
Node *p = newNode();
*p = *now;
return p;
}
/*
bool Bad(Node *now) {
int ls = now->ch[0] ? now->ch[0]->cov : 0;
int rs = now->ch[1] ? now->ch[1]->cov : 0;
return (float)ls > (float)now->cov * Alpha || (float)rs > (float)now->cov * Alpha;
}
*/
void Update(Node *now) {
now->siz = now->cnt + (now->ch[0] ? now->ch[0]->siz : 0) + (now->ch[1] ? now->ch[1]->siz : 0);
now->cov = 1 + (now->ch[0] ? now->ch[0]->cov : 0) + (now->ch[1] ? now->ch[1]->cov : 0);
}
/*
void Dfs(Node *now) {
if (!now) return;
now = Copy(now);
Dfs(now->ch[0]);
if (now->cnt) vec.push_back(now);
else stk.push(now);
Dfs(now->ch[1]);
now->ch[0] = now->ch[1] = NULL;
Update(now);
}
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);
}
*/
void Insert(Node *&now, int k) {
if (!now) {
now = newNode(k);
return;
}
now = Copy(now);
if (k < now->val) Insert(now->ch[0], k);
else if (k == now->val) now->cnt++;
else Insert(now->ch[1], k);
Update(now);
/*if (Bad(now)) {
vec.clear();
Dfs(now);
int len = vec.size();
Rebuild(now, 0, len - 1);
}*/
}
void Remove(Node *&now, int k) {
if (!now) return;
now = Copy(now);
if (k < now->val) {
Remove(now->ch[0], k);
} else if (k == now->val) {
if (now->cnt > 0) now->cnt--;
} else {
Remove(now->ch[1], k);
}
Update(now);
}
int Rank(Node *now, int k) {
if (!now) return 1;
int ls = now->ch[0] ? now->ch[0]->siz : 0;
if (k < now->val) return Rank(now->ch[0], k);
else if (k == now->val) return ls + 1;
else return Rank(now->ch[1], k) + ls + now->cnt;
}
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 + now->cnt) return now->val;
else return Kth(now->ch[1], k - ls - now->cnt);
}
int GetPre(Node *now, int k) {
if (!now) return -INF;
if (now->val >= k) return GetPre(now->ch[0], k);
int ret = GetPre(now->ch[1], k);
return ret == -INF ? (now->cnt ? now->val : GetPre(now->ch[0], k)) : ret;
}
int GetSuc(Node *now, int k) {
if (!now) return INF;
if (now->val <= k) return GetSuc(now->ch[1], k);
int ret = GetSuc(now->ch[0], k);
return ret == INF ? (now->cnt ? now->val : GetSuc(now->ch[1], k)) : ret;
}
int main() {
cin >> n;
int op, ver, k, res;
for (int i = 1; i <= n; i++) {
cin >> ver >> op >> k;
rt[i] = rt[ver];
if (op == 1) {
Insert(rt[i], k);
} else if (op == 2) {
Remove(rt[i], k);
} else if (op == 3) {
res = Rank(rt[i], k);
cout << res << endl;
} else if (op == 4) {
res = Kth(rt[i], k);
cout << res << endl;
} else if (op == 5) {
res = GetPre(rt[i], k);
cout << res << endl;
} else {
res = GetSuc(rt[i], k);
cout << res << endl;
}
}
return 0;
}
```
~~希望本题可以出毒瘤数据卡掉本篇题解~~