题解 P3835 【【模板】可持久化平衡树】
龙之吻—水货
2018-03-31 16:33:34
由于替罪羊树维护平衡不是靠旋转而是靠重构，所以替罪羊树的根是不会变的，这样就可以利用替罪羊树进行可持久化了。
对于3,4,5,6操作，只需要给把要操作的根复制一遍到新根上，其他的和普通的替罪羊树一样；
对于1,2操作先把要操作的根复制一遍到新根，然后进行类似动态开点的线段树，如果要加入（删除）的值比现在节点的大，就new一个左儿子，把原来的节点的所有信息copy到左儿子上，如果要加入（删除）的值比现在节点的小同理操作右儿子，如果要加入（删除）的值等于现在的节点，就直接修改就好了（详见代码）。
然而我这个替罪羊树有个缺点，每次重构的时候不能释放空间，否则会删掉有用的节点，只能通过减少a的值用时间换空间了（如果谁有解决这个的方法，求私信告知）。
附上代码
```
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 5e5 + 7;
const int INF = 2147483647;
double a = 0.50;
int num[1000010], sum, t[1000010];
struct Node{
Node *leftchild, *rightchild;
int val, cnt, size, tot, del;
Node (int val, int cnt) :
val(val),
leftchild(NULL),
rightchild(NULL),
cnt(cnt),
del(0),
tot(0),
size(cnt){}
};
Node *root[maxn], *null;
void Copy(Node *&now, Node *last) {
if (!last) {
now = NULL;
return;
}
now->leftchild = last->leftchild;
now->rightchild = last->rightchild;
now->cnt = last->cnt;
now->del = last->del;
now->size = last->size;
now->tot = last->tot;
now->val = last->val;
}
void UpdateSize(Node *&now) {
if (!now) {
return;
}
now->size = now->cnt;
now->del = now->tot;
if (now->leftchild) {
now->size += now->leftchild->size;
now->del += now->leftchild->del;
}
if (now->rightchild) {
now->size += now->rightchild->size;
now->del += now->rightchild->del;
}
}
void DFS(Node *now) {
if (!now) {
return;
}
DFS(now->leftchild);
if (now->cnt - now->tot) {
num[++sum] = now->val;
t[sum] = now->cnt - now->tot;
}
DFS(now->rightchild);
}
Node *Rebuild(int l, int r) {
Node *now;
if (l > r) {
return NULL;
}
if (l == r) {
now = new Node(num[l], t[l]);
return now;
}
int mid = l + r >> 1;
now = new Node(num[mid], t[mid]);
now->leftchild = Rebuild(l, mid - 1);
now->rightchild = Rebuild(mid + 1, r);
UpdateSize(now);
return now;
}
void Maintain(Node *&now) {
if (!now) {
return;
}
int left_size = now->leftchild ? now->leftchild->size : 0;
int right_size = now->rightchild ? now->rightchild->size : 0;
if ((double)left_size * a > (double)right_size) {
sum = 0;
DFS(now);
now = Rebuild(1, sum);
}
else if ((double)right_size * a > (double)left_size) {
sum = 0;
DFS(now);
now = Rebuild(1, sum);
}
else if(now->del >= now->size / 2 || now->cnt <= now->tot) {
sum = 0;
DFS(now);
now = Rebuild(1, sum);
}
}
Node *Insert(Node *now, int val, Node *last) {
if (!now) {
now = new Node(val, 1);
return now;
}
if (now->val == val) {
now->cnt++;
}
else if(now->val > val) {
now->leftchild = new Node(1, 1);
Copy(now->leftchild, last->leftchild);
now->leftchild = Insert(now->leftchild, val, last->leftchild);
}
else {
now->rightchild = new Node(1, 1);
Copy(now->rightchild, last->rightchild);
now->rightchild = Insert(now->rightchild, val, last->rightchild);
}
UpdateSize(now);
Maintain(now);
return now;
}
Node *Remove(Node *now, int val, Node *last) {
if (!now) {
return now;
}
if (now->val == val) {
now->tot++;
}
else if (now->val > val) {
now->leftchild = new Node(1, 1);
Copy(now->leftchild, last->leftchild);
now->leftchild = Remove(now->leftchild, val, last->leftchild);
}
else {
now->rightchild = new Node(1, 1);
Copy(now->rightchild, last->rightchild);
now->rightchild = Remove(now->rightchild, val, last->rightchild);
}
UpdateSize(now);
Maintain(now);
return now;
}
int Rank(Node *now, int val) {
if (!now) {
return 1;
}
int left_size = now->leftchild ? now->leftchild->size - now->leftchild->del: 0;
if (now->val == val) {
return left_size + 1;
}
if (now->val < val) {
return left_size + now->cnt - now->tot + Rank(now->rightchild, val);
}
else {
return Rank(now->leftchild, val);
}
}
int FindKth(Node *now, int rank) {
if (!now) {
return 0;
}
int left_size = now->leftchild ? now->leftchild->size - now->leftchild->del: 0;
if (rank <= left_size) {
return FindKth(now->leftchild, rank);
}
rank -= left_size;
if (rank <= now->cnt - now->tot) {
return now->val;
}
rank -= now->cnt - now->tot;
return FindKth(now->rightchild, rank);
}
int GetPro(Node *now, int val) {
if(!now) {
return -INF;
}
if (now->val < val) {
if (now->cnt > now->tot) {
return max(now->val, GetPro(now->rightchild, val));
}
return GetPro(now->rightchild, val);
}
else {
return GetPro(now->leftchild, val);
}
}
int GetSuc(Node *now, int val) {
if (!now) {
return INF;
}
if (now->val > val) {
if (now->cnt > now->tot) {
return min(now->val, GetSuc(now->leftchild, val));
}
return GetSuc(now->leftchild, val);
}
else {
return GetSuc(now->rightchild, val);
}
}
int n;
int main() {
scanf("%d", &n);
int _sum = 0;
for (int i = 1; i <= n; i++) {
int flag, x, numb;
scanf("%d %d %d", &numb, &flag, &x);
switch(flag) {
case 1 : {
root[++_sum] = new Node(1, 1);
Copy(root[_sum], root[numb]);
root[_sum] = Insert(root[_sum], x, root[numb]);
break;
}
case 2 : {
root[++_sum] = new Node(1, 1);
Copy(root[_sum], root[numb]);
root[_sum] = Remove(root[_sum], x, root[numb]);
break;
}
case 3 : {
root[++_sum] = new Node(1, 1);
Copy(root[_sum], root[numb]);
printf("%d\n", Rank(root[_sum], x));
break;
}
case 4 : {
root[++_sum] = new Node(1, 1);
Copy(root[_sum], root[numb]);
printf("%d\n", FindKth(root[_sum], x));
break;
}
case 5 : {
root[++_sum] = new Node(1, 1);
Copy(root[_sum], root[numb]);
printf("%d\n", GetPro(root[_sum], x));
break;
}
case 6 : {
root[++_sum] = new Node(1, 1);
Copy(root[_sum], root[numb]);
printf("%d\n", GetSuc(root[_sum], x));
break;
}
}
}
}
```