查找 Search

> 也许，同学间最好的结局就是朋友吧。 $\mu ry$ 是一个可爱的女孩子。 在她所住的小区里有排成一排的 $n$ 个垃圾桶，从左至右第 $i$ 个垃圾桶里都装着编号为 $a_i$ 的垃圾。 $\mu ry$ 不喜欢无序，于是就想把社区里编号和为 $w$ 的垃圾都清在一起。 但是调皮的 $\text{LeverImmy}$ 可能会把某个垃圾桶里的垃圾偷换成另一种。 生气的 $\mu ry$ 想考考 $\text{LeverImmy}$ 一个区间 $[l, r]$ 内是否存在编号和为 $w$ 的垃圾。 但 $\text{LeverImmy}$ 也不会解决这个问题，于是他找到了聪明的你。

给定 $n$ 个垃圾桶，你需要维护一个数据结构，支持以下操作： - `1 pos val` 表示将 第 $pos$ 个垃圾桶里的垃圾的编号换成 $val$； - `2 l r` 询问在 $[l\oplus cnt, r\oplus cnt]$ 内是否存在垃圾编号和为 $w$ 的 **两个** 垃圾桶。 其中 $\oplus$ 表示异或运算，$cnt$ 表示在 **此次询问之前**，答案为 `Yes` 的个数。 对于每个操作 2，若存在请输出 `Yes`，不存在请输出 `No`。 值得注意的是，对于所有询问， $w$ 为 **同一个数**。

第一行共三个整数 $n, m, w$，表示序列长度、接下来的操作个数与 $w$。 第二行共 $n$ 个整数 $a_1, a_2, \cdots, a_n$ 描述了这个每个垃圾桶内垃圾的编号 $a$。 接下来的 $m$ 行，每行三个整数，格式为 `opt x y`。

令操作 2 的次数为 $t$，输出数据共 $t$ 行。 第 $i$ 行表示第 $i$ 个操作 2 的结果，即 `Yes` 或 `No`。

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

Yes
No
Yes

10 20 10
9 3 6 3 3 3 3 1 4 9
1 3 9
1 6 9
2 3 10
1 3 9
2 4 4
1 1 7
1 1 3
1 5 6
1 3 9
2 4 7
1 2 7
2 6 8
1 6 10
2 2 9
1 7 9
2 3 1
1 3 5
1 5 6
1 9 10
1 3 6

Yes
No
No
No
Yes
Yes

本题采用 **捆绑测试**，开启 **O2优化**。 $\text{Subtask 1 (7 pts)}:$ 保证 $1 \le n, m, w \le 2\cdot10^3$，**时限 $1\text{s}$**； $\text{Subtask 2 (20 pts)}:$ 保证 $1 \le n, m, w \le 1\cdot10^5$，$opt = 2$，**时限 $2\text{s}$**； $\text{Subtask 3 (30 pts)}:$ 保证 $1 \le n, m, w \le 1\cdot10^5$，**时限 $2\text{s}$**； $\text{Subtask 4 (43 pts)}:$ 没有特殊限制，**时限 $4\text{s}$**； 对于所有数据， $1 \le n, m, w \le 5\cdot10^5$，$0 \le a_i \le w$。 数据保证对于每个操作，$1 \le pos \le n$，$0 \le val \le w$，$1 \le l \le r \le n$。 由于输入输出量较大，建议使用更快的输入输出方式。 --- #### 输入 #1 解释 第一次操作，询问区间 $[1, 4]$ 中是否有两个数加起来为 $6$，显然有$a_1 + a_4 = 6$，因此输出 `Yes`； 第二次操作，修改 $a_4$ 为 $1$，则序列变为 $[1, 3, 2, 1, 5, 6]$； 第三次操作，询问区间 $[1, 4]$ 中是否有 **两个** 数加起来为 $6$，无，因此输出 `No`。 第四次操作，询问区间 $[2, 6]$ 中是否有两个数加起来为 $6$，显然有 $a_4 + a_5 = 6$，因此输出 `Yes`。