https://www.luogu.org/problemnew/show/P5055

• Copy 节点的时候注意判断你要 Copy 的是不是空节点，Copy 了空节点就 GG 了
• Push Down 的时候两个儿子节点也要可持久化
• 记得输入后异或 last_ans

#include <bits/stdc++.h>

#define NS (200005)
#define FIR first
#define SEC second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

struct N {int d, l, r, k, sz; LL s; bool rev;} e[NS * 70];

int n, root[NS], sz;

int New(int d)
{
int a = ++sz;
memset(&e[a], 0, sizeof(N));
e[a].s = e[a].d = d, e[a].k = rand(), e[a].sz = 1;
return a;
}

int Copy(int x)
{
if (!x) return 0;
int a = New(0);
e[a] = e[x];
return a;
}

void pup(int a)
{
e[a].s = e[e[a].l].s + e[e[a].r].s + e[a].d;
e[a].sz = e[e[a].l].sz + e[e[a].r].sz + 1;
}

void pdown(int a)
{
if (e[a].rev)
{
int &l = e[a].l, &r = e[a].r;
if (l) l = Copy(l), swap(e[l].l, e[l].r), e[l].rev ^= 1;
if (r) r = Copy(r), swap(e[r].l, e[r].r), e[r].rev ^= 1;
e[a].rev = 0;
}
}

int Merge(int a, int b)
{
if (!a || !b) return (a | b);
int c = New(0);
if (e[a].k < e[b].k) e[c] = e[a], pdown(c), e[c].r = Merge(e[c].r, b);
else e[c] = e[b], pdown(c), e[c].l = Merge(a, e[c].l);
pup(c);
return c;
}

PII Split(int a, int d)
{
if (!a) return PII(0, 0);
a = Copy(a), pdown(a);
int l = e[a].l, r = e[a].r;
if (e[l].sz == d) {e[a].l = 0, pup(a); return PII(Copy(l), a);}
if (e[l].sz + 1 == d) {e[a].r = 0, pup(a); return PII(a, Copy(r));}
if (e[l].sz > d)
{
PII tmp = Split(l, d);
e[a].l = tmp.SEC, pup(a);
return PII(tmp.FIR, a);
}
PII tmp = Split(r, d - e[l].sz - 1);
e[a].r = tmp.FIR, pup(a);
return PII(a, tmp.SEC);
}

void Insert(int a, int b, int v)
{
PII tmp = Split(root[v], a);
root[v] = Merge(Merge(tmp.FIR, New(b)), tmp.SEC);
}

void Erase(int a, int v)
{
PII t1 = Split(root[v], a - 1), t2 = Split(t1.SEC, 1);
root[v] = Merge(t1.FIR, t2.SEC);
}

void Rev(int l, int r, int v)
{
PII t1 = Split(root[v], l - 1), t2 = Split(t1.SEC, r - l + 1);
e[t2.FIR].rev ^= 1, swap(e[t2.FIR].l, e[t2.FIR].r);
root[v] = Merge(t1.FIR, Merge(t2.FIR, t2.SEC));
}

LL lst;

void Query(int l, int r, int v)
{
int ts = sz, tr = root[v];
PII t1 = Split(root[v], l - 1), t2 = Split(t1.SEC, r - l + 1);
printf("%lld\n", lst = e[t2.FIR].s), sz = ts, root[v] = tr;
}

int main(int argc, char const* argv[])
{
IN(n), srand(19260817);
for (int i = 1, v, o; i <= n; i += 1)
{
LL a, b;
IN(v), IN(o), IN(a), a ^= lst, root[i] = root[v];
if (o == 1) IN(b), b ^= lst, Insert(a, b, i);
else if (o == 2) Erase(a, i);
else if (o == 3) IN(b), b ^= lst, Rev(a, b, i);
else IN(b), b ^= lst, Query(a, b, i);
}
return 0;
}


#### Remmina

No puzzle that couldn't be solved.