P9995 [Ynoi2000] rspcn

Given an integer sequence $a_1,\dots,a_n$, there are $m$ operations in total. Each operation gives $l, r, x$. First perform a modification, then query how many distinct values there are in $a_1,\dots,a_x$. If $l \le r$, the modification is to sort $a_l,\dots,a_r$ in increasing order; otherwise, the modification is to sort $a_r,\dots,a_l$ in decreasing order.

The first line contains two integers $n, m$. The second line contains $n$ integers $a_1,\dots,a_n$. The next $m$ lines each contain three integers $l \oplus c, r \oplus c, x \oplus c$, describing each operation in order, where $\oplus$ is bitwise XOR, and $c$ is the answer to the previous operation’s query (in particular, for the first operation, $c = 0$).

Output $m$ lines, each containing one integer, in order, representing the answer to the query of each operation.

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078. Constraints: For $20\%$ of the testdata, $n, m \le 10^3$. For another $20\%$ of the testdata, $a_i \le 10$. For another $20\%$ of the testdata, $a_i \le 100$. For another $20\%$ of the testdata, $n, m \le 10^5$. For $100\%$ of the testdata, $1 \le a_i \le n$, $1 \le l, r, x \le n$, and $1 \le n, m \le 10^6$. Translated by ChatGPT 5