P7125 [Ynoi2008] rsmemq

Given a sequence $a$ of length $n$, define $x$ to be the mode of the interval $[l, r]$ if and only if there does not exist $y$ such that the number of occurrences of $y$ in the interval $[l, r]$ is **greater than** the number of occurrences of $x$ in the interval $[l, r]$. There are $m$ queries. Each query gives $l, r$. For each query, find how many ordered pairs $(l', r')$ satisfy $l \le l' \le r' \le r$, and the length of interval $[l', r']$ is odd, and $(l' + r') / 2$ **(note that this is an index, not the value at that index)** is the mode of the interval $[l', r']$.

The first line contains two integers $n$ and $m$. The next line contains $n$ integers describing the sequence. The following $m$ lines each contain two integers $l$ and $r$, representing one query.

Output $m$ lines in total, each being the answer for the corresponding query.

Idea: yummy&nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477&czr, Data: nzhtl1477(partially uploaded) For $100\%$ of the testdata: $1 \le n, m \le 5 \times 10^5$, $1 \le l \le r \le n$, $1 \le a_i \le n$. All values are integers. Sample explanation: In $[1,4]$, the subintervals that satisfy the conditions are $[1,3]$, $[2,2]$. In $[1,3]$, the subintervals that satisfy the conditions are $[1,3]$, $[2,2]$. In $[2,6]$, the subintervals that satisfy the conditions are $[2,2]$. In $[7,10]$, the subintervals that satisfy the conditions are $[7,7]$, $[8,10]$, $[10,10]$. In $[4,10]$, the subintervals that satisfy the conditions are $[7,7]$, $[6,8]$, $[5,9]$, $[4,10]$, $[8,10]$, $[10,10]$. In $[3,7]$, the subintervals that satisfy the conditions are $[7,7]$. Translated by ChatGPT 5