启发式分裂
启发式分裂
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133321898
启发式分裂和启发式合并类似
对于一个数据结构，我们要对它进行分裂的时候，如果暴力拆成两个数据结构，很容易被卡
这个时候我们就可以考虑启发式分裂，把小的分出去，大的保留
在分治、set等题目中有广泛应用
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-26
分治常见Trick——启发式分裂+中间相遇法：CF1181E2
分治常见Trick——启发式分裂+中间相遇法：CF1181E2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133323437 https://www.luogu.com.cn/problem/CF1181E2 首先E1，也就是分治应该很好想 考虑到E2，首先看到题目是二维平面，有很多种分割方法，所以我们可以考虑拆维。 拆完之后我们考虑枚举分界点。枚举分界点暴力遍历过大，于是自然而然的，我们可以考虑中间相遇法。 但如果优雅的维护对应的集合呢？朴素思路使用s...
2023-09-23
具有部分单调性的区间个数计数问题——考虑分治：GZOI2023Day1T3
具有部分单调性的区间个数计数问题——考虑分治：GZOI2023Day1T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133218885 询问有多少区间满足 Sum×Len≤Max2Sum\times Len\le Max^2Sum×Len≤Max2 发现在 MaxMaxMax 定的情况下，显然满足单调性 对于此类题目，可以考虑分治处理 对于当前分治区间，我们采用的分治策略是左右独立算+计算跨区间 显然必然是一段后缀加一段前缀。 先枚举左端点，然后根据上...
2023-09-26
中间相遇法（分治类问题非等大分治的平衡做法）
中间相遇法（分治类问题非等大分治的平衡做法） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133321701 分治，如果分成两半大小不一样，很容易被卡到 O(n2)O(n^2)O(n2) 在某些题目中，利用中间相遇法，我们可以优化这个过程 其优化的前提是分治的大头在找分界点 复杂度不用证，很好理解吧 这层找地越久，下一层就越均匀
2023-10-17
分治类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′...
2026-10-07
二阶差分生成函数优化dp + NTT + cdq优化NTT：CCPC2026网络赛G
二阶差分生成函数优化dp + NTT + cdq优化NTT：CCPC2026网络赛G Growing Prefix Span - Problem - QOJ.ac 哭了，这道题调了10多个小时，打了无数个补丁，终于调出来了 好，首先一开始肯定是要处理一下 [Li,Ri][L_i,R_i][Li,Ri]，变成合法区间，然后判断一下无解。 然后我们可以列一个很显然的 O(n2)O(n^2)O(n2) 的dp。f(i,j)f(i,j)f(i,j) 代表前 iii 个数长为 jjj，显然有： f(i,j)=f(i−1,j)×(j−i+1)+2∑k<jfi−1,kf(i,j)=f(...
2023-11-06
偏序关系用分治优化建图：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 这是个二维偏序问题，我们考虑用分...