cdq分治_解题技巧

发表于 2024-03-09 更新于 2024-03-19 分类于解题技巧阅读次数： Waline：本文字数： 134 阅读时长 ≈ 1 分钟

和普通分治的区别

普通分治是左、右两边各处理各的，然后合并一下结果；

cdq分治是左、右两边各处理各的之后，再处理某一半区间对另一半区间的贡献。

sort排序可以放到最后，以优化时间复杂度，比如：

void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  cdq(l, mid), cdq(mid + 1, r);
  ...
  sort(a + l, a + r + 1, cmpx);
}