P11833

考场上别人怎么都写的线段树，就我写的 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)$ 的了。

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