# Irelia

### 题解 P3835 【【模板】可持久化平衡树】

posted on 2019-06-02 20:31:59 | under 题解 |

## 不加平衡措施的BST

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