CDQ分治模型 / p3810

前言

CDQ分治是主要解决一类和点对相关的分治方法，并且要求离线，不太好支持修改，它和点分治有着异曲同工之妙，它主要处理线性数据，而点分治主要处理树上数据

核心思路是将线性数据 [ l , r ] [l, r] [l,r] 拆成两份： [ l , m i d ] , [ m i d + 1 , r ] [l, mid], [mid+1, r] [l,mid],[mid+1,r]递归处理两个区间，再找 ( i , j ) , i ∈ [ l , m i d ] , j ∈ [ m i d + 1 , r ] (i,j),i\in[l,mid],j\in[mid+1,r] (i,j),i∈[l,mid],j∈[mid+1,r]这样的点对，CDQ分治它是一种思想，不是具体算法

它主要可以解决以下三类问题：

1. 解决和点对有关的问题
2. 1维动态规划的优化与转移
3. 通过 CDQ 分治，将一些动态问题转化为静态问题

注：2可以由1转化， d p i = 1 + max ⁡ j = 1 i − 1 d p j [ a j < a i   &   b j < b i ] dp_i = 1 + \max_{j=1}^{i-1}dp_j[a_j