CDQ分治_占坑

准备系统地学习一波CDQ分治,持续更新中...

首先,CDQ分治也还是分治的一种,只不过普通分治是独立的解决两个子问题,而CDQ分治还要计算第一个子问题对于第二个的影响。

CDQ分治几乎都是用来解决多维偏序对的问题。

使用CDQ分治的前提条件:

  • 修改操作对询问的贡献独立,修改操作互不影响效果
  • 题目允许使用离线算法。

可以用CDQ解决的经典问题:

例题1:BZOJ 3262  陌上花开

对第一位x排序,然后仅需求(y, z)的顺序对,用树状数组维护即可。

例题2:BZOJ 2683  N*N(N≤1e5)矩阵内单点修改、区间求和

原文地址:https://www.cnblogs.com/zinyy/p/9332442.html