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