北京笔记Day1

分治

（略）

复杂度分析

$ T(n)=2 * T(n/2)+O(kn) \Rightarrow O(kn*logn) $

CDQ分治

1. 适用条件:

   1. 离线算法

   2. 每次修改操作对答案贡献独立，操作互不干扰

2. 简易模型

   计算 $ [mid+1,r] $

   计算 $ [mid+1,r] $

3. 三维偏序 $ (a,b,c) $

   1. 按 $ a $ 属性排序

   2. 用两个指针扫 $ b_{i}\leq b_{j} $

   3. 用树状数组维护 $ c $ 属性

4. 例题 (玄学时间)

   1. BZOJ 1176

      …

   2. BZOJ 2716

      …

   3. HDU 5127

      …

   4. Cash

      …

   5. BZOJ 4137

整体二分

1. 条件:

   1. 答案具有二分性

   2. 修改独立，修改对询问独立

   3. 离线算法

2. 形如: $ solve(l,r,S) $

3. 例题:

   1. 静态区间第K小 (主席树)

   2. BZOJ 3110

      1. 线段树套平衡树 (愚蠢的做法)

      2. 权值线段树套线段树

      3. 整体二分

   3. BZOJ 2527

Meet in the middle

1. 其实就是双向搜索

2. 例题

   1. 给出一个DAG,求一个点A到另一个点B路径长度为L的方案数

      1. 求出从A和B出发的距离为 L/2 的点及其方案数

      2. ans=集合交集乘积的和

   2. ABCDEF

   3. A