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

「THUPC 2021 初赛」区间众数

题目描述

给定一个长为 nn 的序列 aa,定义 xx 为区间 [l,r][l, r] 的众数当且仅当不存在 yy 使得 yy 在区间 [l,r][l, r] 中的出现次数大于 xx 在区间 [l,r][l,r] 中的出现次数。

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

输入格式

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

其中 1n5×1051 \le n \le 5\times {10}^51m1061 \le m \le {10}^61lrn1 \le l \le r \le n1ain1 \le a_i \le n,所有数值为整数。

输出格式

输出共 mm 行,表示每个询问对应的答案。

样例

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,4] 中满足条件的子区间为 [1,3][1, 3][2,2][2, 2]

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

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

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

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

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

来源

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

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