P6019 [Ynoi2010] Brodal queue

The background is not related to the task and can be skipped.

Given a sequence $a$ of length $n$, each position has a color. There are $m$ operations. You need to support: `1 l r x`: Set all numbers in the interval $[l,r]$ to $x$. `2 l r`: Query how many pairs $(i,j)$ satisfy $l \leq i < j \leq r$ and $a_i = a_j$. This problem is forced online. For each operation, the input $l,r,x$ must be $\operatorname{xor}$-ed with (the last answer $\bmod 2^{32}$). That is, you can store the last answer using the `unsigned int` data type. If there has been no query before, the last answer is $0$. The output answer is not taken $\bmod 2^{32}$.

The first line contains two integers $n, m$. The second line contains $n$ integers representing the sequence $a$. Then follow $m$ lines. Each line is in the form `1 l r x` or `2 l r`, representing the operations above.

For each operation of type $2$, output one line with one integer representing the answer.

Idea: nzhtl1477, Solution: nzhtl1477&ccz181078, Code: ccz181078, Data: nzhtl1477. Note: This problem uses **bundled tests**. You can get the score for a subtask only after you pass all test points in that subtask. For $1\%$ of the testdata, it is Sample 1. For another $9\%$ of the testdata, there are no modification operations. For another $19\%$ of the testdata, $n,m\leq 500$. For another $19\%$ of the testdata, the length of each modified interval does not exceed $5$. For another $19\%$ of the testdata, the testdata is guaranteed to be random. For $100\%$ of the testdata, $1\leq n,m\leq 2\times 10^5$, $1\leq a_{i},x\leq n$, $1\leq l\leq r\leq n$. Translated by ChatGPT 5