A6430. 「CodePlus 2017 11 月赛」Yazid 的新生舞会
编程题
省选/NOI-
知识点
题目描述
这道题是没有舞伴的 Yazid 用新生舞会的时间出的。
---
Yazid 有一个长度为 $n$ 的序列 $A$，下标从 $1$ 至 $n$。显然地，这个序列共有 $\frac{n\left( n+1\right)}{2}$ 个子区间。
对于任意一个子区间 $[l,r]$，如果该子区间内的众数在该子区间的出现次数严格大于 $\frac{r-l+1}{2}$（即该子区间长度的一半），那么 Yazid 就说这个子区间是「新生舞会的」。
所谓众数，即为该子区间内出现次数最多的数。特别地，如果出现次数最多的数有多个，我们规定值最小的数为众数。
现在，Yazid 想知道，共有多少个子区间是「新生舞会的」。
---
Yazid 有一个长度为 $n$ 的序列 $A$，下标从 $1$ 至 $n$。显然地，这个序列共有 $\frac{n\left( n+1\right)}{2}$ 个子区间。
对于任意一个子区间 $[l,r]$，如果该子区间内的众数在该子区间的出现次数严格大于 $\frac{r-l+1}{2}$（即该子区间长度的一半），那么 Yazid 就说这个子区间是「新生舞会的」。
所谓众数，即为该子区间内出现次数最多的数。特别地，如果出现次数最多的数有多个，我们规定值最小的数为众数。
现在，Yazid 想知道，共有多少个子区间是「新生舞会的」。
输入格式
第一行 $2$ 个用空格隔开的非负整数 $n,type$，表示序列的长度和**数据类型**。数据类型的作用将在「子任务」中说明。
第二行 $n$ 个用空格隔开的非负整数，依次为 $A_1,A_2,\dots ,A_n$，描述这个序列。
第二行 $n$ 个用空格隔开的非负整数，依次为 $A_1,A_2,\dots ,A_n$，描述这个序列。
输出格式
输出一行一个整数，表示答案。
输入输出样例
输入 #1
5 0 1 1 2 2 3
输出 #1
10
说明/提示
对于所有数据，保证 $1 \leqslant n \leqslant 500000$，$0\leqslant A_i\leqslant n-1$。
---
来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/郑林楷 命题/王聿中 验题/郑林楷
Git Repo：https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。
---
来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/郑林楷 命题/王聿中 验题/郑林楷
Git Repo：https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。