P8257 [CTS2022] Prokhorovka

Given a sequence $a_1,\dots,a_n$ and a total of $m$ queries, each query provides $l,r$. You need to compute the bitwise XOR sum of the weights of all pairs $(L,R)$ that satisfy $l\le L\le R\le r$. The weight of a pair $(L,R)$ is $|\{a_i\mid L\le i\le R\}|$.

Read from standard input. The first line contains two integers $n\ m$. The next line contains $n$ integers $a_1,\dots,a_n$. The next $m$ lines each contain two integers $l\ r$, representing one query.

Write to standard output. Output $m$ lines, in order, each being the answer to the corresponding query.

For $5\%$ of the testdata, $1\le n,m\le 100$. For $10\%$ of the testdata, $1\le n,m\le 5000$. For $20\%$ of the testdata, $1\le n,m\le 10^5$. For $30\%$ of the testdata, $1\le n,m\le 2\times 10^5$. For $40\%$ of the testdata, $1\le n,m\le 3\times 10^5$. For $50\%$ of the testdata, $1\le n,m\le 3.5\times 10^5$. For another $10\%$ of the testdata, $m=n^2$. For another $10\%$ of the testdata, for all $i=1\cdots n$, $a_i\le 2$. For another $10\%$ of the testdata, for all $i=1\cdots n$, $a_i\le 10$. For $100\%$ of the testdata, $1\le n,m\le 4\times 10^5$, $1\le a_i\le n$, and all values are integers. Each category of testdata forms a subtask. Translated by ChatGPT 5