#124. 任何邪恶? 终将绳之以法!

    ID: 124 Type: Default 1000ms 256MiB Tried: 20 Accepted: 6 Difficulty: 8 Uploaded By: Tags>福建师范大学第26届低年级程序设计竞赛

任何邪恶? 终将绳之以法!

Time limit: 1 seconds

Memory limit: 256 megabytes

It wasn't only wickedness and scheming that made people unhappy, it was confusion and misunderstanding.—Atonement, Writer, Ian McEwan

题目描述

“本以为抓个小贼,没想到捅了老窝”

昊京在小贼的带领下进入了小贼的老窝,老窝的形状是一个包含nn个节点的满二叉树。二叉树以11为根节点,对于编号为xx的非叶子节点,都有两个儿子,左儿子编号为2x2x,右儿子编号为2x+12x+1。初始时nn个节点上都没有小贼。

现在有qq次行动,每次行动分为3类:

1 x1 \ x: 昊京站在节点x,询问每个小贼与昊京的距离之和

2 x2 \ x: 节点x出现小贼

3 x3 \ x: 节点x上的小贼消失

对于每次操作1,你都需要输出对应的答案。

满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。

输入

11行输入两个正整数n,qn, q

22行到第q+1q+1行,每行输入两个数type,xtype, x。其中typetype为行动的类别,xx为目标节点。

输出

对于每个type=1type=1的询问,需要输出对应的答案,答案之间以空行分隔。

限制

n,q<=131071,type{1,2,3} n, q <= 131071, type \in \{1,2,3\} ,保证 n=2h1n=2^h-1,其中h为正整数;

保证对于每个2操作,目标节点xx原本没有小贼;

保证对于每个3操作,目标节点xx原本有小贼。

7 6
1 3
2 4
2 7
1 3
3 4
1 3
0
4
1

样例解释

对于第一次询问,老窝中并没有小贼,距离之和为0;

对于第二次询问,节点4和节点7中有小贼,距离之和为3+1=4;

对于第三次询问,节点7中有小贼,距离之和为1。

Postscript

For someone special: Is not general incivility the very essence of love?