P7139 [THUPC 2021 Preliminary] Range Mode

## 注意： 本题不提供评测，需要提交本题请到 [[Ynoi2008]rsmemq](/problem/P7125)。

Given a sequence $a$ of length $n$, define $x$ to be a mode of the interval $[l, r]$ if and only if there does not exist $y$ such that the number of occurrences of $y$ in $[l, r]$ is **greater than** the number of occurrences of $x$ in $[l, r]$. There are $m$ queries. Each query gives $l, r$. For each query, find how many pairs $(l', r')$ satisfy $l \le l' \le r' \le r$, and the length of $[l', r']$ is odd, and $(l' + r') / 2$ **(note that this is an index, not the value at that index)** is a mode in the interval $[l', r']$. ## Note: This problem does not provide an online judge. To submit for this problem, please go to [[Ynoi2008]rsmemq](/problem/P7125).

The first line contains two integers $n, m$. The next line contains $n$ integers describing the sequence. The following $m$ lines each contain two integers $l, r$, representing a query. Constraints: $1 \le n \le 5 \times {10}^5$, $1 \le m \le {10}^6$, $1 \le l \le r \le n$, $1 \le a_i \le n$. All values are integers.

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

**[Sample Explanation #1]** In $[1, 4]$, the subintervals that satisfy the condition are $[1, 3]$, $[2, 2]$. In $[1, 3]$, the subintervals that satisfy the condition are $[1, 3]$, $[2, 2]$. In $[2, 6]$, the subintervals that satisfy the condition are $[2, 2]$. In $[7, 10]$, the subintervals that satisfy the condition are $[7, 7]$, $[8, 10]$, $[10, 10]$. In $[4, 10]$, the subintervals that satisfy the condition are $[7, 7]$, $[6, 8]$, $[5, 9]$, $[4, 10]$, $[8, 10]$, $[10, 10]$. In $[3, 7]$, the subintervals that satisfy the condition are $[7, 7]$. **[Source]** From the preliminary round of THUPC 2021 (Tsinghua University Student Programming Contest and Collegiate Invitational Contest). Resources such as editorials can be found at . Translated by ChatGPT 5