P11833

cosf · 2025-03-02 19:29:56 · 题解

考场上别人怎么都写的线段树，就我写的 odt。

我们发现，假设当前每个人的位置在 p_i，那么必然有 p_i \lt p_{i + 1}。这个关系是严格的，不太好处理，所以让所有 a_i, b_i 减去 i，这个关系就变成不严格的 p_i \le p_{i + 1}。

本题的结论就是按照 t_i 从小到大排序，然后分别将 i 推向 b_i，同时将 p_i 到 b_i 中的所有人都推向 b _i。具体证明其他题解应该都写了，就不写了。

可以发现，假设 p_i < b_i，则我们需要的是将所有 p_j \in [p_i, b_i) 的 j 移动到 b_i，移动的步数是 \sum_j b_i - p_j。计算结束后，还会把所有这样的 p_j 赋值为 b_i。

因此可以考虑 odt。令线段 (l, r, v) 表示当前 p_l, \dots, p_r = v，则我们只需把所有 v \in [p_i, b_i) 的线段的 (r - l + 1)(b_i - v) 加起来即可。

由于初始时有 O(n) 个线段，每次操作只会加入一个线段，因此总共的线段数是 O(n) 级别的。又由于每个线段在访问一次后就会被删除，因此最终的复杂度就是 O(n\log n) 的了。

但是此做法常数有点大，不知道会不会挂分。