[HNSDFZ #6] 可持久化线段树

题目描述

现有一序列$A$。您需要实现一棵可持久化线段树，用于实现如下操作：

• A v p x：对于版本v的序列，给$A_p$增加$x$.
• Q v l r：对于版本v的序列，询问$A_{[l,r]}$的区间和。
• C v：拷贝一份版本v的序列，编号为当前版本总数+1.

注意版本号从$1$开始；版本$1$的序列，所有元素均为$0$.

格式

输入格式

第一行，两个正整数$n,t$，表示序列的长度和操作个数。
接下来$t$行，每行一个操作，格式如题目描述所述。

保证任何输入的数都是正整数。

输出格式

对于每一个Q操作，输出一行一个整数，表示对应的区间和。

样例数据

样例输入

5 5
A 1 2 3
Q 1 1 4
C 1
A 2 3 2
Q 2 1 4

样例输出

3
5

解释

第一次操作后，版本1的序列为：0 3 0 0 0.
第二次操作询问版本1的$A_{[1,4]}$区间和，答案为$0+3+0+0=3$.
第三次操作将版本1的序列复制到版本2.
第四次操作后，版本2的序列为：0 3 2 0 0.
第五次操作询问版本2的$A_{[1,4]}$区间和，答案为$0+3+2+0=5$.

数据规模与约定

对于$20\%$的数据，有$n \leq 1000 , m \leq 100$.
对于$60\%$的数据，有$n \leq 100000 , m \leq 1000$.
对于$100\%$的数据，有$n \leq 1000000 , m \leq 1000000$.