#PQZ1034x5022. 【模板】线段树

【模板】线段树

【模板】线段树

题目描述

标题: 【模板】线段树 - Problem - QOJ.ac

#5022. 【模板】线段树

Statistics

The problem was used in the following contests:

给定一个长度为 n 的序列 a1,a2,⋯,an。你需要进行共 q 次下面两种操作:

  • 1 l r:将 a[l,r] 替换为它的异或差分。形式化地说,对于每个 l<i≤r ,令 bi=aixor⁡ai−1 ,然后对于每个 l<i≤r,将 ai 替换为 bi。
  • 2 pos: 查询 apos 的值。

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

输入格式

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

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

第三行包含 n 个整数 a1,a2,⋯,an。

接下来 q 行,每行若干个数,表示一个操作。若操作为第一种操作,则此行包含三个数 1 l r 。若操作为第二种操作,则此行包含两个数 2 pos。

输出格式

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

前 q2 行,每行输出一个整数,表示该操作的答案。

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

样例一

input

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

output

9
4
12
1
0
5
4
12
0

explanation

初始时 a=[1,1,5,1,9,4] 。

第一个操作要求输出 a5 ,此时 a5=9 ,故输出 9 。

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

第三个操作要求输出 a4 ,此时 a4=4 ,故输出 4 。

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

第五个操作要求输出 a6 ,此时 a6=12 ,故输出 12 。

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

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

样例二 - 样例九

见下发文件 2.in - 9.in,2.out - 9.out。对于第 i+1 个样例,该样例满足子任务 i 的限制且 T=i。

数据范围

对于所有数据,保证 1≤n≤2.5×105,1≤q≤105,0≤ai<230,1≤l≤r≤n,1≤pos≤n 。

子任务编号 n≤ q≤ 特殊性质 分值 子任务依赖 1 2×103 2×103 无 8 无 2 2.5×105 105 A 4 3 B 7 4 CD 13 5 DE 12 6 D 16 5 7 E 11 8 无 29 1∼7

特殊性质 A:∀i≥2,ai=0 。

特殊性质 B:0≤ai≤1 。

特殊性质 C:记序列 a 中非零位置个数为 c ,则 c≤100 。

特殊性质 D:操作 1 满足 l=1,r=n。

特殊性质 E:没有操作 2 。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

官方测试点 25 个;落地 9 个;时限 3.0s,内存 512MB。

样例

样例 1

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

样例 2

1
10 64
178 181 183 184 188 189 190 191 192 195
1 3 5
2 10
2 8
1 4 9
2 10
2 2
1 1 5
2 5
2 3
2 3
1 2 7
2 3
1 3 9
2 7
1 1 8
1 2 8
2 7
2 7
2 5
2 2
2 7
2 5
1 2 7
1 8 10
1 2 3
1 6 10
1 5 6
1 5 7
2 4
1 5 10
1 2 5
2 3
1 4 7
2 5
1 2 10
1 3 10
1 2 5
2 3
1 1 3
1 2 7
2 10
1 2 9
2 4
1 2 6
2 10
1 4 6
1 2 9
2 4
2 2
2 5
2 10
1 6 8
2 9
1 3 9
1 6 8
2 4
1 6 8
2 4
1 2 6
2 7
2 7
1 1 6
1 5 6
2 3
195
191
195
181
4
2
2
5
7
1
1
3
181
1
3
15
2
12
2
6
189
6
186
7
9
6
125
13
13
189
189
183
178
181
183
10
4
14
189
179
122
6

数据来源:QOJ 公开题包官方 .in/.out;本题落地 9 个测试点,QOJ 元数据标注官方共 25 点,覆盖级别:部分官方测试点。时限 3.0s,内存 512MB。按 Hydro 默认逐字节比对判定。