[笔记]CDQ 分治

前

CDQ 分治是一种分治算法，或者说是一种思想，其主要内容是：将序列通过递归的方式分给左右两个区间，每一个子问题只处理跨左右区间的贡献。
使用 CDQ 分治建立在排序的基础上，这也说明 CDQ 分治必须离线使用。
CDQ 分治可以解决的问题：

• 与点对有关的问题（数点 & 偏序）。
  
• 将带修改 & 查询的动态问题，转化为静态问题。
  
• 优化 1D / 1D 动态规划的转移。
  

本质上，这些问题都属于“点对之间的贡献问题”。
点对有关问题

一些概念

偏序

\(k\) 维偏序问题，即在一个由 \(n\) 个 \(k\) 元组构成的集合 \(\{(a_{1,1},\dots,a_{1,k}),\dots,(a_{n,1},\dots,a_{n,k})\}\) 中，求与 \((a_{i,1},\dots,a_{i,k})\) 满足某种偏序关系，即 \((a_{i,1},\dots,a_{i,k})\prec(a_{j,1},\dots,a_{j,k})\) 的 \(j\) 的个数。
这其中，“\(\prec\)” 是一种具有自反性、反对称性、传递性的二元关系，例如：

• 二维偏序 \((a,b)\) 中，\(a_i\le a_j,\ b_ia_j,\ b_i\le b_j,c_i\le c_j\)
  
• \(\dots\)
  

逆序对就是常见的二维偏序问题，此时这个集合可以写为 \(\{(1,a_1),\dots,(n,a_n)\}\)。
数点

\(k\) 维数点问题，即在一个由 \(n\) 个 \(k\) 元组构成的集合 \(\{(a_{1,1},\dots,a_{1,k}),\dots,(a_{n,1},\dots,a_{n,k})\}\) 中，求满足下列条件的 \(k\) 元组 \((a_{j,1},\dots,a_{j,k})\) 的个数 / 权值和：

• \(l_1\le a_{j,1}\le r_1\)
  
• \(\dots\)
  
• \(l_n\le a_{j,n}\le r_n\)
  

可以理解为在 \(k\) 维平面上给定若干点，查询某个区域内点的个数。
二维偏序

<blockquote>
例 \(1\)：给定 \(n\) 个二元组，对每一组 \((x_i,y_i)\)，求满足 \(x_j