加载中...

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

发表于2023-09-23|OI（高中）2023-2024赛季

|总字数:196|阅读时长:1分钟|浏览量:

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

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133218885

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

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

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

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

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

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

$Max$ 定

所以右边界已经限定

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

定右端点同理

在这里插入图片描述

文章作者: zhangxixi

文章链接: http://zhangxixi2008.github.io/post/d3ac6b34

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！

相关推荐

偏序关系用分治优化建图：ARC165F

偏序关系用分治优化建图：ARC165F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134253598 https://atcoder.jp/contests/arc165/tasks/arc165_f 首先可以建图，然后变成求字典序最小的的拓扑排序然后发现这样复杂度会炸，观察连边的条件是什么： li<ljl_i<l_jli<lj ri<rjr_i<r_jri<rj 这是个二维偏序问题，我们考虑用分...

中间相遇法（分治类问题非等大分治的平衡做法）

中间相遇法（分治类问题非等大分治的平衡做法）本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133321701 分治，如果分成两半大小不一样，很容易被卡到 O(n2)O(n^2)O(n2) 在某些题目中，利用中间相遇法，我们可以优化这个过程其优化的前提是分治的大头在找分界点复杂度不用证，很好理解吧这层找地越久，下一层就越均匀

分治构造：P9384

分治构造：P9384 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134366235 https://www.luogu.com.cn/problem/P9384 分治构造是很常见的一种构造不能有三元环和五元环，考虑推广出去，也就是不能有奇环那如果我们让每种颜色都为二分图，那么必然满足考虑 0-9 总共10个数字，数据范围1000，考虑 210>10002^{10}>1000210>1000 ，考虑 logloglog 级复杂度的做...

分治类DP：1017T3

分治类dp：1017T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133884752 http://cplusoj.com/d/senior/p/SS231017C 感觉可以分治某个区间 [l,r][l,r][l,r] ，且他们都是在下面 kkk 已经选的基础上然后肯定要枚举最大值，最大值越长越好 Hint 1 Hint 2 f(l,r,k)f(l, r, k)f(l,r,k) 可以通过枚举 midmidmid ，或者枚举 k′k'k′...

FWT小结本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132922605 核心思想：把 a,ba,ba,b 化成 fwt(a),fwt(b)fwt(a),fwt(b)fwt(a),fwt(b) ，相乘后再化为 aaa 化的过程用的是分治所以和FFT其实一模一样 OR / AND 卷积不需要什么技巧，暴力分治转移即可每次分治下去，相当于位数减一注意合并过程中我们是计算对应位的贡献因为其它位的贡献我们在分治下去时已经计算了后面区间其他数贡献到前面...

启发式分裂

启发式分裂本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133321898 启发式分裂和启发式合并类似对于一个数据结构，我们要对它进行分裂的时候，如果暴力拆成两个数据结构，很容易被卡这个时候我们就可以考虑启发式分裂，把小的分出去，大的保留在分治、set等题目中有广泛应用

数据加载中