啥时候「文艺平衡树」成了 Splay 的代称了……
果断写了个 FHQ Treap，然后 30pts。
求助大佬之后发现标记下传时也要新建结点。
以及合并的时候不必新建结点，因为分裂时已经新建了，否则会 MLE。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
using namespace std;
const int N = 2e5;
int n;
long long lastans;
struct node
{
int rnd,sz,rev;
long long val,sum;
int lson,rson;
} tree[(N << 7) + 10];
int rt[N + 10];
inline int new_node(long long v = 0)
{
static int tot = 0;
tree[++tot].val = v;
tree[tot].sum = v;
tree[tot].rnd = rand();
tree[tot].sz = 1;
return tot;
}
inline int copy_node(int p)
{
int ret = new_node();
tree[ret] = tree[p];
return ret;
}
inline void up(int p)
{
tree[p].sz = tree[ls(p)].sz + 1 + tree[rs(p)].sz;
tree[p].sum = tree[ls(p)].sum + tree[p].val + tree[rs(p)].sum;
}
inline void down(int p)
{
if(tree[p].rev)
{
if(ls(p))
ls(p) = copy_node(ls(p));
if(rs(p))
rs(p) = copy_node(rs(p));
swap(ls(p),rs(p));
if(ls(p))
tree[ls(p)].rev ^= 1;
if(rs(p))
tree[rs(p)].rev ^= 1;
tree[p].rev = 0;
}
}
void split(int p,int k,int &x,int &y)
{
if(!p)
{
x = y = 0;
return ;
}
down(p);
if(tree[ls(p)].sz < k)
x = copy_node(p),split(rs(x),k - tree[ls(p)].sz - 1,rs(x),y),up(x);
else
y = copy_node(p),split(ls(y),k,x,ls(y)),up(y);
}
int merge(int x,int y)
{
if(!x || !y)
return x | y;
down(x),down(y);
if(tree[x].rnd < tree[y].rnd)
{
rs(x) = merge(rs(x),y);
up(x);
return x;
}
else
{
ls(y) = merge(x,ls(y));
up(y);
return y;
}
}
int main()
{
srand(19260817);
scanf("%d",&n);
int cnt = 0;
int v,op;
long long a,b;
int x,y,z;
while(n--)
{
scanf("%d%d",&v,&op);
if(op == 1)
{
scanf("%lld%lld",&a,&b);
a ^= lastans,b ^= lastans;
split(rt[v],a,x,y);
rt[++cnt] = merge(merge(x,new_node(b)),y);
}
else if(op == 2)
{
scanf("%lld",&a);
a ^= lastans;
split(rt[v],a,x,z);
split(x,a - 1,x,y);
rt[++cnt] = merge(x,z);
}
else if(op == 3)
{
scanf("%lld%lld",&a,&b);
a ^= lastans,b ^= lastans;
split(rt[v],b,x,z);
split(x,a - 1,x,y);
tree[y].rev ^= 1;
rt[++cnt] = merge(merge(x,y),z);
}
else
{
scanf("%lld%lld",&a,&b);
a ^= lastans,b ^= lastans;
split(rt[v],b,x,z);
split(x,a - 1,x,y);
printf("%lld\n",lastans = tree[y].sum);
rt[++cnt] = merge(merge(x,y),z);
}
}
}