P7125.md

[Ynoi2008] rsmemq

题目描述

给定一个长为 $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$ 表示一次询问。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

2
0
2
1
0
3
1
6
0
1

提示

Idea：yummy&nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477&czr，Data：nzhtl1477(partially uploaded)

对于 $100%$ 的数据，其中 $1\le n,m\le 5\times 10^5$，$1\le l\le r\le n$，$1\le a_i\le n$，所有数值为整数。

样例解释：

$[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]$。