主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 C: 可持久化数据结构

问题 C: 可持久化数据结构

时间限制: 3 Sec  内存限制: 256 MB
提交: 91  解决: 22
[提交][状态][讨论版]

题目描述

所谓的可持久化数据结构,就是保存这个数据结构的所有历史版本。现在你的任务就是要维护一个可持久化数据结构。
有一个长度为n的整数数列A,最初所有元素都为0。还有一个辅助变量C,一开始也是0。现有如下两种操作:
1 i x :将A[i^C]的值加上x,然后将C设为更改后的A[i^C]的值。
2 l r t: 查询t次操作1之后的[l^C, r^C]的区间和(注意:C是进行此次2询问时的C,而不是t次1操作后的C,用于强制在线),然后将C设为此次询问的答案。保证输入合法。
(其中“^”符号表示异或操作)

输入


第一行两个整数n(1<=n<=1000000), q(1<=q<=100000),表示数列的长度和询问的个数。
接下来q行,每行为1 i x或2 l r t,含义如上文所说。(x<=1000)

输出

对于每一个操作2,在单独一行输出其答案。

样例输入

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

样例输出

3
15

提示

[提交][状态][讨论版]