具有部分单调性的区间个数计数问题——考虑分治：GZOI2023Day1T3

询问有多少区间满足 $Sum\times Len\le Ma{x}^2$

发现在 $Max$ 定的情况下，显然满足单调性

对于此类题目，可以考虑分治处理

对于当前分治区间，我们采用的分治策略是左右独立算+计算跨区间

显然必然是一段后缀加一段前缀。

先枚举左端点，然后根据上面结论，我们必须使：

• $Max$ 定

所以右边界已经限定

剩下的满足单调性，二分即可

定右端点同理