[AdditionalFile6746.zip](file://AdditionalFile6746.zip?type=additional_file)

#6746. 「THUPC 2021 初赛」区间众数

标签: 传统 | 时间限制: 8000 ms | 内存限制: 256 MiB |

题目描述

给定一个长为 $n$ 的序列 $a$，定义 $x$ 为区间 $[l, r]$ 的众数当且仅当不存在 $y$ 使得 $y$ 在区间 $[l, r]$ 中的出现次数大于 $x$ 在区间 $[l,r]$ 中的出现次数。

有 $m$ 次询问，每次询问给出 $l, r$，求有多少二元组 $(l',r')$ 满足 $l\le l'\le r'\le r$，且 $[l', r']$ 的区间长度为奇数，且 $(l' + r') / 2$（注意这里是下标而不是下标对应的值）是区间 $[l', r']$ 中的众数。

输入格式

输入的第一行包含两个数 $n, m$。
之后一行 $n$ 个数表示这个序列。
之后 $m$ 行，每行两个数 $l, r$ 表示一次询问。

其中 $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$，所有数值为整数。

输出格式

输出共 $m$ 行，表示每个询问对应的答案。

样例

输入

10 10
2 2 2 1 2 7 7 9 6 10
1 4
4 4
1 3
2 6
6 6
7 10
2 6
4 10
3 5
3 7

输出

2
0
2
1
0
3
1
6
0
1

$[1,4]$ 中满足条件的子区间为 $[1, 3]$，$[2, 2]$。

$[1, 3]$ 中满足条件的子区间为 $[1, 3]$，$[2, 2]$。

$[2, 6]$ 中满足条件的子区间为 $[2, 2]$。

$[7, 10]$ 中满足条件的子区间为 $[7, 7]$，$[8, 10]$，$[10, 10]$。

$[4, 10]$ 中满足条件的子区间为 $[7, 7]$，$[6, 8]$，$[5, 9]$，$[4, 10]$，$[8, 10]$，$[10, 10]$。

$[3, 7]$ 中满足条件的子区间为 $[7, 7]$。

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。