Problem Description

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.

Input Format

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 Format

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

9 7
2 2 8 8 2 8 2 1 3
2 2 2
3 7 6
6 7 1
9 6 7
10 11 10
7 0 5
5 1 7

1
2
1
2
3
2
2

Hint

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