Luogu4062 [Code+#1] Yazid 的新生舞会

题意：对于序列 ，若有某个数的出现次数超过 ，则称之为好序列。

给出长度为 的序列 ，问有多少个区间是好序列。

，时限 。

---

将出现次数过半的数称为强众数。显然，某个序列若有强众数，则至多只有一个。

所以，可以枚举强众数 ，然后计算能贡献的区间。

构造新序列 ，令 为 的前缀和。

则区间 的强众数为 的充要条件是 ：

于是可以转化为二维偏序问题。

---

但对每个 做一次二维偏序显然无法通过。注意到 中 的个数总和是 的，考虑借助这一性质减小复杂度。

令 ，在两个 之间的大量连续 中， 是一个公差为 的等差序列。

不难发现，按照 划分，即可得到共 个等差序列。

于是，问题变为等差序列的偏序问题。

---

显然，一条等差序列内部是没有偏序的，于是我们逐个插入等差序列，并计算与前面的等差序列之间的贡献。

记 为等于 的数的个数，加入一个等差序列等价于区间加。

查询时，对于等差序列 ，贡献为 。可以差分为 状物。

再令 为 的差分，则问题变为 。即单点修改，查询三阶前缀和。

树状数组分别维护 的前缀和即可。

复杂度 。