纳米电脑主机¶
- 参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：64 MB
背景故事¶
帝国研究员用纳米电脑主机分析无人机的升级方案。研究记录是一列非负整数，每种连续的研究组合都有一个异或值。研究员会修改单条记录，也会查询一段记录内所有连续组合的异或值之和。请帮助主机及时回答。
形式化问题描述¶
维护长度为 \(n\) 的非负整数数组 \(a_1,\ldots,a_n\) ，依次处理 \(q\) 个操作：
1 l r：查询所有满足 \(l\le i\le j\le r\) 的非空子区间 \([i,j]\) 的异或值之和，即
\[
\sum_{i=l}^{r}\sum_{j=i}^{r}(a_i\oplus a_{i+1}\oplus\cdots\oplus a_j)
\]
2 p v：把 \(a_p\) 赋值为 \(v\) ，不是加上 \(v\) .
其中 \(\oplus\) 表示按位异或。外层求和使用普通整数加法，不再异或，也不取模。每次查询使用当时的数组。
输入格式¶
第一行 \(n,q\) .第二行 \(n\) 个整数表示初始数组。之后 \(q\) 行按上述格式给出操作。
输出格式¶
每次操作 1 输出一行一个整数。若没有查询，则不输出任何内容。
样例 1¶
输入¶
10 10
10 3 8 2 6 10 7 6 1 8
1 2 4
2 10 8
1 1 3
2 8 4
2 6 8
2 2 10
1 9 9
2 3 7
1 6 6
1 8 8
输出¶
43
42
1
8
4
解释¶
第一次查询的数组为 \([3,8,2]\) ，六个子区间的异或值为 \(3,8,2,11,10,9\) ，总和为 \(43\) .
样例 2¶
输入¶
2 4
65536 65536
1 1 2
2 1 0
1 1 2
1 1 1
输出¶
131072
131072
0
解释¶
数值 \(65536\) 的第 \(16\) 位为 \(1\) ，必须计入。长度为二的子区间在修改前异或值为 \(0\) ，修改后为 \(65536\) .
数据范围与保证¶
- \(1\le n,q\le100000\) .
- 初始值和赋值参数均满足 \(0\le a_i,v\le65536\) .
- \(1\le l\le r\le n\) ，\(1\le p\le n\) .
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |