日常不理解算法本质

周末给 afewdgre 讲题，偶遇简单时间轴问题，拼尽全力勉强战胜

何为时间轴

• 特点：单向。

  前面的修改会影响后面的查询；反过来，后面的修改不会影响前面的查询。

• 在大部分 DS 题目中，顺序操作是满足这个条件的。考虑不存在明显操作时间轴的问题，通常处理方式是扫描线：即用坐标轴当时间轴，这样做的前提条件也是『前面的修改影响后面的查询，但后面的修改不影响前面的查询』。这里拿给 afewdgre 讲的矩形面积并举例。

  矩形面积并中，把一段 \(x\) 坐标上，每个 \(y\) 上矩形存在的状态转化成『某个时刻，一段 \(y\) 是否被覆盖』，矩形的增删则用差分的方式维护。

CDQ 分治

• 在需求时间轴的需求上，额外要求：

  修改之间无依赖，或者说，单次修改对询问的影响是可求的。

• 这样就可以分治。大部分分治的基本目标都是，使相同的计算不用被多次进行。

• 每层 CDQ 会统计每个 \([l,mid]\) 的修改对 \([mid+1,r]\) 询问的影响。

好像讲完了？