#P16092. [Oni2017]bvarcolaci

    ID: 15303 传统题 3000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-根号分治暴力枚举容斥原理等差数列求和一维前缀和增量维护

[Oni2017]bvarcolaci

题目描述

给定一个长度为 N 的数组。请计算有多少个连续子数组存在多数元素。

对于一个长度为 K 的数组,若某个值出现次数至少为 floor(K/2)+1,则称该值为多数元素。

输入格式

第一行包含整数 N。

第二行包含 N 个整数,表示数组元素。

输出格式

输出一个整数,表示存在多数元素的连续子数组数量。

数据范围与约定

  • 1 <= N <= 250000;
  • 所有数组元素都在 1..N 之间;
  • 连续子数组由原数组中连续的一段位置唯一确定。

样例

6
1 2 1 2 3 2
10

样例解释

所有长度为 1 的子数组都有多数元素;除此之外还有 4 个连续子数组有多数元素。