P5278 Arithmetic Genius ⑨ and Arithmetic Progressions

Arithmetic Genius ⑨ really likes playing with arithmetic progressions. One day, he gave you a sequence of length $n$, where the $i$-th number is $a_i$. He wants to test you. Each time, he will give a query $l, r, k$ and ask whether the numbers in the interval $[l, r]$, after being sorted in increasing order, can form an arithmetic progression with common difference $k$. Of course, he will also keep modifying some element. To avoid being looked down on by him, you must answer all queries quickly and correctly. Note: A sequence with only one number is also an arithmetic progression.

The first line contains two positive integers $n, m$, representing the length of the sequence and the number of operations. The second line contains $n$ integers, in order, representing each number in the sequence $a_i$. The next $m$ lines each start with a number $\text{op}$. If $\text{op} = 1$, then two integers $x, y$ follow, meaning to modify $a_x$ to $y$. If $\text{op} = 2$, then three integers $l, r, k$ follow, meaning a query. **In this problem, $x, y, l, r, k$ are all encrypted, and you need to decrypt them by XORing with the number of `Yes` you have output before.**

Output several lines. For each query, if it can form an arithmetic progression, output `Yes`; otherwise output `No`.

Constraints For $100\%$ of the testdata, $1 \le n, m \le 3 \times 10^5$, and $0 \le a_i, y, k \le 10^9$. Translated by ChatGPT 5