QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

# 5022. 【模板】线段树

Statistics

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。你需要进行共 $q$ 次下面两种操作:

  • 1 l r:将 $a[l,r]$ 替换为它的异或差分。形式化地说,对于每个 $l < i ≤ $r ,令 $b_i=a_i \operatorname{xor} a_{i-1}$ ,然后对于每个 $l < i≤r$,将 $a_i$ 替换为 $b_i$。
  • 2 pos: 查询 $a_{pos}$ 的值。

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

输入格式

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

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

第三行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

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

输出格式

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

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

接下来 $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]$ 。

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

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

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

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

第五个操作要求输出 $a_6$ ,此时 $a_6=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.in2.out - 9.out。对于第 $i+1$ 个样例,该样例满足子任务 $i$ 的限制且 $T=i$。

数据范围

对于所有数据,保证 $1 \leq n \leq 2.5 \times 10^5$,$1 \leq q \leq 10^5$,$0 \leq a_i < 2^{30}$,$1 \leq l \leq r \leq n$,$1 \leq pos \leq n$ 。

子任务编号 $n \le$ $q \le $ 特殊性质 分值 子任务依赖
$1$ $2 \times 10^3$ $2 \times 10^3$ $8$
$2$ $2.5 \times 10^5$ $10^5$ A $4$
$3$ B $7$
$4$ CD $13$
$5$ DE $12$
$6$ D $16$ $5$
$7$ E $11$
$8$ $29$ $1 \sim 7$

特殊性质 A:$\forall i \geq 2, a_i=0$ 。

特殊性质 B:$0 \leq a_i \leq 1$ 。

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

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

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