CF1580C Train Maintenance

标签

暴力 + 分块

思路

对 $x_i + y_i$ 进行根号分治. 分为两类

1> $x_i + y_i \leq \sqrt{m}$

因为 $x_i + y_i \leq \sqrt{m}$, 所以这样的 $x_i + y_i$ 最多有 $\sqrt{m}$ 种 (废话😒) ， 然后对于每一个 $x_k + y_k$ 维护一个线性表 (可以支持 $O(1)$ 的单点修改和查询) $a[i][j]$， 用来维护 $x_k + y_k = i$ 的火车对模 $i$ 为 $j$ 的时刻的贡献, 每加入或删除一个火车时可以直接暴力修改，查询时直接暴力统计每个线性表。

2> $x_i + y_i > \sqrt{m}$

注意每次询问的时刻是一天一天的递增的， 所以可以用差分。

因为 $x_i + y_i > \sqrt{m}$ 所以火车维修的时间段数 $< \sqrt{m}$ , 然后用差分进行修改就行了。

悟

1. 按照修改区间的长度进行根号分治。
2. 对于长度小于 $\sqrt{m}$ 的修改区间，长度最多有 $\sqrt{m}$ 种

坑

注意在撤销一辆车时如果当前时刻在一个维修段内的话要给答案减一。