#P15817. [2025年山东集训第三轮]还原论

[2025年山东集训第三轮]还原论

题目描述

小 σ\sigma 给了你一个长度为 nn 的序列 a1,a2,…,ana_1,a_2,\ldots,a_n。小 σ\sigma 需要你执行共 qq 次下面两种操作:

  1. 1 l r:将 a[l,r]a[l,r] 替换为它的异或差分。形式化地说,对于每个 l<i≤rl<i\le r,令

    bi=aixor⁡ai−1,b_i=a_i\operatorname{xor} a_{i-1},

    然后对于每个 l<i≤rl<i\le r,将 aia_i 替换为 bib_i。其中 ala_l 保持不变。

  2. 2 pos:查询 aposa_{pos} 的值。

所有操作执行完后,你还需要回答最终的 aa 序列。

输入格式

第一行包含一个整数 TT,表示该数据满足第 TT 个子任务的限制。

第二行包含两个整数 n,qn,q,分别表示序列长度和操作个数。

第三行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

接下来 qq 行,每行若干个数,表示一个操作:

  • 若操作为第一种操作,则此行包含三个整数 1 l r;
  • 若操作为第二种操作,则此行包含两个整数 2 pos。

输出格式

设共有 q2q_2 个第二种操作,则输出共包含 q2+nq_2+n 行。

前 q2q_2 行,每行输出一个整数,表示对应查询操作的答案。

接下来 nn 行,每行输出一个整数,表示最终的 aa 序列。

样例 0

输入

1
6 6
1 1 5 1 9 4
2 5
1 2 5
2 4
1 3 6
2 6
1 1 6

输出

9
4
12
1
0
5
4
12
0

解释

初始时:

a=[1,1,5,1,9,4]。a=[1,1,5,1,9,4]。

第 11 个操作查询 a5a_5 的值,此时 a5=9a_5=9,输出 99。

第 22 个操作要求将 a[2,5]a[2,5] 替换为它的异或差分。a[2,5]a[2,5] 为 [1,5,1,9][1,5,1,9],它的异或差分为 [1,4,4,8][1,4,4,8],故操作执行完后:

a=[1,1,4,4,8,4]。a=[1,1,4,4,8,4]。

第 33 个操作查询 a4a_4 的值,此时 a4=4a_4=4,输出 44。

第 44 个操作要求将 a[3,6]a[3,6] 替换为它的异或差分。a[3,6]a[3,6] 为 [4,4,8,4][4,4,8,4],它的异或差分为 [4,0,12,12][4,0,12,12],故操作执行完后:

a=[1,1,4,0,12,12]。a=[1,1,4,0,12,12]。

第 55 个操作查询 a6a_6 的值,此时 a6=12a_6=12,输出 1212。

第 66 个操作要求将 a[1,6]a[1,6] 替换为它的异或差分。a[1,6]a[1,6] 为 [1,1,4,0,12,12][1,1,4,0,12,12],它的异或差分为 [1,0,5,4,12,0][1,0,5,4,12,0],故操作执行完后:

a=[1,0,5,4,12,0]。a=[1,0,5,4,12,0]。

最终的 aa 序列为 [1,0,5,4,12,0][1,0,5,4,12,0]。

数据范围与提示

对于所有数据,保证:

$$1\le n\le 2.5\times 10^5, \quad 1\le q\le 10^5, \quad 0\le a_i<2^{30}, \quad 1\le l\le r\le n, \quad 1\le pos\le n。$$
子任务编号 子任务分值 n≤n\le q≤q\le 特殊性质
1 10 2×1032\times 10^3 无
2 2.5×1052.5\times 10^5 10510^5 A
3 B
4 CD
5 DE
6 D
7 E
8 30 无

特殊性质:

  • A:∀i≥2, ai=0\forall i\ge 2,\ a_i=0。
  • B:0≤ai≤10\le a_i\le 1。
  • C:记序列 aa 中非零位置个数为 cc,则 c≤100c\le 100。
  • D:操作 1 满足 l=1,r=nl=1,r=n。
  • E:没有操作 2。