P6617 Search

> Perhaps the best ending between classmates is just being friends. $\mu ry$ is a lovely girl. In the community where she lives, there are $n$ trash bins lined up in a row. From left to right, the $i$-th trash bin contains a piece of trash with label $a_i$. $\mu ry$ does not like disorder, so she wants to put all trash whose labels sum to $w$ together. However, the naughty $\text{LeverImmy}$ may swap the trash in some bin into another kind. Angry, $\mu ry$ wants to test whether $\text{LeverImmy}$ can answer: in an interval $[l, r]$, does there exist trash in **two** bins whose labels sum to $w$? But $\text{LeverImmy}$ cannot solve this problem either, so he turns to the smart you.

Given $n$ trash bins, you need to maintain a data structure that supports the following operations: - `1 pos val` means changing the label in the $pos$-th trash bin to $val$. - `2 l r` asks whether there exist **two** trash bins in $[l\oplus cnt, r\oplus cnt]$ whose labels sum to $w$. Here, $\oplus$ denotes the XOR operation, and $cnt$ is the number of answers equal to `Yes` **before this query**. For each operation of type 2, output `Yes` if such a pair exists; otherwise output `No`. Note that for all queries, $w$ is **the same number**.

The first line contains three integers $n, m, w$, representing the length of the sequence, the number of subsequent operations, and $w$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, describing the label $a$ in each trash bin. The next $m$ lines each contain three integers in the format `opt x y`.

Let the number of type 2 operations be $t$. Output $t$ lines in total. The $i$-th line is the result of the $i$-th type 2 operation, i.e., `Yes` or `No`.

This problem uses **bundled tests**, with **O2 optimization** enabled. $\text{Subtask 1 (7 pts)}:$ Guaranteed $1 \le n, m, w \le 2\cdot10^3$, **time limit $1\text{s}$**. $\text{Subtask 2 (20 pts)}:$ Guaranteed $1 \le n, m, w \le 1\cdot10^5$, $opt = 2$, **time limit $2\text{s}$**. $\text{Subtask 3 (30 pts)}:$ Guaranteed $1 \le n, m, w \le 1\cdot10^5$, **time limit $2\text{s}$**. $\text{Subtask 4 (43 pts)}:$ No special restrictions, **time limit $4\text{s}$**. For all testdata, $1 \le n, m, w \le 5\cdot10^5$, $0 \le a_i \le w$. The testdata guarantees that for each operation, $1 \le pos \le n$, $0 \le val \le w$, and $1 \le l \oplus cnt \le r \oplus cnt \le n$. Since the input and output are large, faster I/O methods are recommended. --- #### Explanation for Sample Input #1 In the first operation, we query whether there are two numbers in the interval $[1, 4]$ that sum to $6$. Obviously, $a_1 + a_4 = 6$, so output `Yes`. In the second operation, modify $a_4$ to $1$, so the sequence becomes $[1, 3, 2, 1, 5, 6]$. In the third operation, query whether there are **two** numbers in the interval $[1, 4]$ that sum to $6$. There are none, so output `No`. In the fourth operation, query whether there are two numbers in the interval $[2, 6]$ that sum to $6$. Obviously, $a_4 + a_5 = 6$, so output `Yes`. Translated by ChatGPT 5