# Irelia

### 题解 P5055 【【模板】可持久化文艺平衡树】

posted on 2019-06-01 21:59:43 | under 题解 |

### 前置知识

• 会用FHQ Treap通过文艺平衡树， 熟悉区间反转的标记下传。以上在文艺平衡树题解里都有。

• 写过可持久化数据结构，比如可持久化数组，明白可持久化原理。

### 本题解法

#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;
}