[Ynoi2016] 炸脖龙 II
题目背景
瞬间…
真要说的话,比瞬间还要短暂。
羽咲往悬崖的方向飞去。
瘦小的羽咲,比想象中更轻易地飞侠了悬崖。
我急忙跑向悬崖边。
然而,飞奔而出之后,方向并不是那么容易改变。
我失去了平衡,就这么摔倒在地。
只能一直用目光追寻着羽咲的身影。
飞出悬崖的羽咲。
身体浮在半空中。
在下一瞬间,便听任自由落体定律…径直坠下陡峭的悬崖
![](https://cdn.luogu.com.cn/upload/pic/21200.png)
细长的双眼…注视着我的眼睛。
这是幻觉吗…还是现实…
卓司的指尖捅破了头盖骨…
这根本不可能的吧…人的手劲如何能够捏破头盖骨…
这毫无疑问是幻觉…不可能存在于现实中…
这种事,习武的我是最清楚不过的…
这种根本不可能的事…
尽管如此…
我的意识仍朦胧起来…
已经无法与这个世界保持联系了…
“我…收下皆守哥哥的身体了哦…”
![](https://cdn.luogu.com.cn/upload/pic/21201.png)
司空见惯的风景。
比之前看到的风景更让人眼熟。
我所熟悉的风景…
![](https://cdn.luogu.com.cn/upload/pic/21202.png)
“我会把他带走的…所以你走吧…”
“卓司…那个电波小子,就让我把他带走…”
“所以你就前进吧…”
“在无法登上的坡道的尽头”
“你不能停滞不前,必须前去迎接小羽”
“好啦,打起精神来…皆守”
“在这里告别吧…”
![](https://cdn.luogu.com.cn/upload/pic/21203.png)
轻飘飘的感觉。
瞬间,感觉到了周围空气的急速变冷。
扬起的灰尘伴随月光的照耀,在空中废物。
告别了永不相交的平行,我和羽咲被吸进了…
垂直下落的世界。
月光映照出羽咲身体的轮廓。
地面没有影子。
宛如高空飞翔一般…
远方传来警笛声。
在苍穹之下反复回想。
我仰望无限的天空,笔直坠下。
一刻也不远看丢,在我上方的羽咲…
月在笑。
神在笑。
笑这滑稽的姿势。
笑这喜剧般的悲剧。
群星旋转。
如舞如蹈。
夜空上的神,正嘲弄着我们。
就想把空瓶子扔在地上的天真的孩子一样…
世界变得一片空虚。
![](https://cdn.luogu.com.cn/upload/pic/21204.png)
望不到尽头的坡道…
遥远而模糊的坡道…
宛如…我们就漫步在这样的世界中一般…
就算在意坡道的前方也毫无用处。
我们就在这坡道上快乐地走着。
![](https://cdn.luogu.com.cn/upload/pic/21205.png)
题目描述
您在打galgame,突然听说苏联解体了,于是您发现您永远看不到一个活着的苏联人了,很郁闷,于是开始写一道数据结构题:
这是一道模(du)拟(liu)题。
你需要维护一棵包含 $n$ 个结点有根有序树(也就是说每个点的孩子是有“从左到右”的顺序的),初始根为 $1$,支持以下几个操作:
`A(x,y)`:对 $x$ 进行路径压缩,即将 $x$ 到根路径上除了根之外的点的父亲设为根,这些点在根的孩子中的顺序保持原先路径上从浅到深的顺序。
`B(x,y)`:将根的孩子 $x,y$($x$ 在 $y$ 左边)以及之间的点按顺序展开成一条路径,$x$ 仍与根相连,涉及到的点原先的孩子都移至路径右侧。
`C(x,y)`:将树的根设为 $x$,此时原先在根到 $x$ 路径左侧的点仍在左侧且先相对顺序不变,右侧同理,$x$ 的孩子在 $x$ 成为根后在 $x$ 到原先的根的路径的右侧。
`D(x,y)`:给 $x$ 到根的路径上每个点的点权同时加一个数,并在这之后求 $x$ 到根的路径上的点权和。
`E(x,y)`:保证 $x$ 和 $y$ 父亲相同且 $x$ 在 $y$ 左侧,对在 $x$ 的父亲的孩子中,$x$ 到 $y$ 之间(含 $x,y$)的每个点的点权加上 $x+y$,并在这之后求这些点的点权和。
`F(x,y)`:给 $x$ 添加一个孩子 $y$,在最右边,这个操作在其它所有操作之前进行,用于描述树的初始形态。
输入输出格式
输入格式
第一行两个整数 $n,q$,分别表示树的结点数和操作次数。
接下来 $q$ 行,每行表示一个操作。
输出格式
对每个 `D` 或 `E` 操作,输出一行,表示答案对 $2^{32}$ 取模的结果。
输入输出样例
输入样例 #1
20 30
F(1,2)
F(1,3)
F(1,7)
F(1,9)
F(9,5)
F(3,8)
F(3,20)
F(3,6)
F(8,15)
F(8,19)
F(20,14)
F(20,12)
F(6,13)
F(6,18)
F(13,4)
F(12,11)
F(12,17)
F(17,10)
F(17,16)
E(3,9)
E(8,6)
A(12,0)
D(4,6)
E(2,7)
B(3,12)
D(4,6)
C(8,0)
D(13,5)
D(1,7)
E(12,14)
输出样例 #1
36
42
56
89
95
105
90
61
说明
Idea:ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078
$2\leq n\leq 10^5$,$n\leq q\leq 2\times 10^5$,$0\leq x,y \leq n$。
保证操作合法。
为了对称,所有操作都有两个参数 $x,y$,但实际上 `A`,`C` 操作中不需用到 $y$,数据保证此时 $y=0$。
前 $n-1$ 个操作一定是 `F` 操作,保证 $n-1$ 次操作后得到一棵以 $1$ 为根的树,且以后不会再出现 `F` 操作。
注意到 `A`,`B`,`C`,`F` 操作都有关于孩子顺序的规定,可以参照样例解释进行直观的理解。
共 $10$ 组数据。