具有部分单调性的区间个数计数问题—

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

Qres821 • 2023年09月24日 01:26 • 1年前 • 编程日记 • 阅读(3) • 违法举报

询问有多少区间满足 $Sum\times Len\le Max^2$

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

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

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

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

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

所以右边界已经限定

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

定右端点同理

在这里插入图片描述文章来源地址https://uudwc.com/A/wo3Ow

原文地址:https://blog.csdn.net/zhangtingxiqwq/article/details/133218885

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请联系站长进行投诉反馈，一经查实，立即删除！