题解 P5055 【【模板】可持久化文艺平衡树】
Ireliaღ
2019-06-01 21:59:43
**提供指针版`FHQ Treap`题解**
### 前置知识
- 会用`FHQ Treap`通过文艺平衡树， 熟悉区间反转的标记下传。以上在文艺平衡树题解里都有。
- 写过可持久化数据结构，比如可持久化数组，明白可持久化原理。
### 本题解法
大体思路都一样。为了保证每次操作对历史版本不产生影响，在`PushDown()`和`Split()`的操作时复制节点。因为每次`Merge()`前都会`Split()`，所以`Merge()`时就不需要复制节点了。
具体代码如下
```cpp
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 2e5 + 5;
const int INF = 1e9 + 7;
int Rand() {
static LL seed = 0x131309d;
return seed = ((seed * 233333LL) ^ 12345678LL) % INF;
}
struct Node{
int val, pri, siz;
bool tag;
LL sum;
Node *ch[2];
Node(int val = 0) : val(val) {
pri = Rand();
siz = 1;
sum = val;
ch[0] = ch[1] = NULL;
tag = false;
}
};
Node *rt[MAXN];
int n, m;
LL cur;
Node *Copy(Node *now) {
Node *ret = new Node;
if (now) *ret = *now;
return ret;
}
void Update(Node *now) {
now->siz = (LL)(now->ch[0] ? now->ch[0]->siz : 0) + (LL)(now->ch[1] ? now->ch[1]->siz : 0) + 1;
now->sum = (LL)(now->ch[0] ? now->ch[0]->sum : 0) + (LL)(now->ch[1] ? now->ch[1]->sum : 0) + (LL)now->val;
}
void PushDown(Node *now) {
if (!now->tag) return;
swap(now->ch[0], now->ch[1]);
if (now->ch[0]) {
now->ch[0] = Copy(now->ch[0]);
now->ch[0]->tag ^= 1;
}
if (now->ch[1]) {
now->ch[1] = Copy(now->ch[1]);
now->ch[1]->tag ^= 1;
}
now->tag = false;
}
void Split(Node *now, int k, Node *&l, Node *&r) {
if (!now) {
l = r = NULL;
return;
}
PushDown(now);
int ls = now->ch[0] ? now->ch[0]->siz : 0;
if (k <= ls) {
r = Copy(now);
Split(r->ch[0], k, l, r->ch[0]);
Update(r);
} else {
l = Copy(now);
Split(l->ch[1], k - ls - 1, l->ch[1], r);
Update(l);
}
}
Node *Merge(Node *a, Node *b) {
if (!a || !b) return a ? a : b;
if (a->pri <= b->pri) {
PushDown(b);
b->ch[0] = Merge(a, b->ch[0]);
Update(b);
return b;
} else {
PushDown(a);
a->ch[1] = Merge(a->ch[1], b);
Update(a);
return a;
}
}
void Insert(Node *&root, int k, int val) {
Node *a, *b;
Split(root, k, a, b);
root = Merge(a, Merge(new Node(val), b));
}
void Remove(Node *&root, int pos) {
Node *a, *b, *c, *d;
Split(root, pos, d, c);
Split(d, pos - 1, a, b);
if (b) delete b;
root = Merge(a, c);
}
void Reverse(Node *&root, int l, int r) {
Node *a, *b, *c, *d;
Split(root, r, d, c);
Split(d, l - 1, a, b);
if (b) b->tag ^= 1;
root = Merge(a, Merge(b, c));
}
LL Query(Node* &root, int l, int r) {
Node *a, *b, *c, *d;
Split(root, r, d, c);
Split(d, l - 1, a, b);
LL ans = b ? b->sum : 0LL;
root = Merge(a, Merge(b, c));
return ans;
}
void Init() {
ios :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
cur = 0LL;
}
void Work() {
int op, ver;
LL p, x, l, r;
for (int i = 1; i <= n; i++) {
cin >> ver >> op;
rt[i] = rt[ver];
if (op == 1) {
cin >> p >> x;
p ^= cur; x ^= cur;
Insert(rt[i], p, x);
} else if (op == 2) {
cin >> p;
p ^= cur;
Remove(rt[i], p);
} else if (op == 3) {
cin >> l >> r;
l ^= cur; r ^= cur;
Reverse(rt[i], l, r);
} else {
cin >> l >> r;
l ^= cur; r ^= cur;
cur = Query(rt[i], l, r);
cout << cur << endl;
}
}
}
int main() {
Init();
Work();
return 0;
}
```