1558 : 小白找好区间Ⅱ(hard version)

时间限制:1 Sec 内存限制:256 MiB 提交:4 正确:4

题目描述

本题有对应的 $easy \ version$ ，两者的区别在于问法有所不同，请仔细读题。

在去年的新生赛中，同学们已经帮小白找到了 “好区间” ，可是时过境迁，如今好区间的定义也发生了变化，同学们还能和以前一样找到 “好区间” 的数目吗？

小白有 $n$ 个长度为 $3$ 的字符串，他对 $byl$ 这个字符串很感兴趣，你的任务是统计这个数组内 "好区间" 的数量。

对于区间 $[l,r] \in [1,n] ,l \leq r$ ，在此区间中，设 $byl$ 这个字符串出现的次数为 $p1$ ，其他字符串出现的次数为 $p2$ ，如果有 $p1>k \times p2$ ，那么称区间 $[l,r]$ 为一个好区间。