分治
(略)
复杂度分析
T(n)=2∗T(n/2)+O(kn)⇒O(kn∗logn)
CDQ分治
适用条件:
离线算法
每次修改操作对答案贡献独立,操作互不干扰
简易模型
计算 [mid+1,r]
计算 [mid+1,r]
三维偏序 (a,b,c)
按 a 属性排序
用两个指针扫 bi≤bj
用树状数组维护 c 属性
例题
(玄学时间)
整体二分
条件:
答案具有二分性
修改独立,修改对询问独立
离线算法
形如: solve(l,r,S)
例题:
Meet in the middle
其实就是双向搜索例题
给出一个DAG,求一个点A到另一个点B路径长度为L的方案数
求出从A和B出发的距离为 L/2 的点及其方案数
ans=集合交集乘积的和
ABCDEF
A
v1.5.2