#6253. 「CodePlus 2017 11 月赛」Yazid 的新生舞会

内存限制:256 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

这道题是没有舞伴的 Yazid 用新生舞会的时间出的。


Yazid 有一个长度为 nn 的序列 AA,下标从 11nn。显然地,这个序列共有 n(n+1)2\frac{n\left( n+1\right)}{2} 个子区间。

对于任意一个子区间 [l,r][l,r],如果该子区间内的众数在该子区间的出现次数严格大于 rl+12\frac{r-l+1}{2}(即该子区间长度的一半),那么 Yazid 就说这个子区间是「新生舞会的」。

所谓众数,即为该子区间内出现次数最多的数。特别地,如果出现次数最多的数有多个,我们规定值最小的数为众数。

现在,Yazid 想知道,共有多少个子区间是「新生舞会的」。

输入格式

第一行 22 个用空格隔开的非负整数 n,typen,type,表示序列的长度和数据类型。数据类型的作用将在「子任务」中说明。

第二行 nn 个用空格隔开的非负整数,依次为 A1,A2,,AnA_1,A_2,\dots ,A_n,描述这个序列。

输出格式

输出一行一个整数,表示答案。

样例

样例输入 1

5 0
1 1 2 2 3

样例输出 1

10

样例解释 1

「新生舞会的」子区间有 [1,1],[1,2],[1,3],[2,2],[2,4],[3,3],[3,4],[3,5],[4,4],[5,5][1,1],[1,2],[1,3],[2,2],[2,4],[3,3],[3,4],[3,5],[4,4],[5,5]1010 个。

样例输入/输出 2

见页面顶部「附加文件下载」中的 2.in2.ans

样例输入/输出 3

见页面顶部「附加文件下载」中的 3.in3.ans

样例输入/输出 4

见页面顶部「附加文件下载」中的 4.in4.ans

数据范围与提示

对于所有数据,保证 1n5000001 \leqslant n \leqslant 5000000Ain10\leqslant A_i\leqslant n-1


来自 CodePlus 2017 11 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/郑林楷 命题/王聿中 验题/郑林楷
Git Repo:https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。