P5048 [Ynoi2019 Mock Contest] Yuno loves sqrt technology III


You are given a sequence $a$ of length $n$ and $m$ queries. For each query, you need to output the number of occurrences of the mode in a given interval, and the queries are forced to be online.

The first line contains two integers $n, m$. The second line contains $n$ integers representing the sequence. Then follow $m$ lines, each containing two numbers representing the query interval. This problem is forced to be online: in each query, the input numbers should be $\operatorname{xor}$ with $lastans$. For the first query, $lastans = 0$ by default.

Output $m$ lines, each line contains one integer representing the answer to the query.

$1\leq n, m, a_i \leq 5\times 10^5$。 There exists an $O( n^{1.48541} )$ algorithm. Source By nzhtl1477. Translated by ChatGPT 5