BZPRO

#5110. [CodePlus2017]Yazid 的新生舞会

内存限制：256 MiB 时间限制：40 Sec
提交 提交记录 讨论

题目描述

Yazid有一个长度为n的序列A，下标从1至n。显然地，这个序列共有n(n+1)/2个子区间。对于任意一个子区间[l,r]
，如果该子区间内的众数在该子区间的出现次数严格大于(r?l+1)/2（即该子区间长度的一半），那么Yazid就说这
个子区间是"新生舞会的"。所谓众数，即为该子区间内出现次数最多的数。特别地，如果出现次数最多的数有多个
，我们规定值最小的数为众数。现在，Yazid想知道，共有多少个子区间是"新生舞会的"

输入格式

第一行2个用空格隔开的非负整数n,type，表示序列的长度和数据类型。数据类型的作用将在子任务中说明。
第二行n个用空格隔开的非负整数，依次为A1,A2,...,An，描述这个序列。
N<=500000,0<=Type<=3
对于所有数据，保证 0 ≤ Ai ≤ n ? 1。
对于 type = 0 的数据，没有任何特殊约定。
对于 type = 1 的数据，保证 Ai ∈ {0, 1}。
对于 type = 2 的数据，保证序列 A 的众数在整个序列中的出现次数不超过 15。
对于 type = 3 的数据，保证 Ai ≤ 7。

输出格式

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

样例

样例输入


			
5 0

1 1 2 2 3

样例输出


			
10

//"新生舞会的" 子区间有 [1, 1], [1, 2], [1, 3], [2, 2], [2, 4], [3, 3], 

[3, 4], [3, 5], [4, 4], [5, 5]共 10 个。

数据范围与提示

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/郑林楷　命题/王聿中　验题/郑林楷

Git Repo：https://git.thusaac.org/publish/CodePlus201711

本次比赛的官方网址：cp.thusaac.org

感谢腾讯公司对此次比赛的支持。

BZPRO Powered by Remmina.
Github Repository