题解：AT_abc389_f [ABC389F] Rated Range

· · 题解

F - Rated Range

先离线，发现初始时 X<Y，那么从开始到结束的所有过程 X\le Y，即相对顺序不发生改变。

把询问的每个值拍到序列上，发现一次操作的影响是一段区间。

为了维护每个询问的值，需维护以下操作：

  1. 区间加 1。
  2. 找到 \ge x 的第一个下标。
  3. 找到 \le y 的最后一个下标。

由于序列是单调的，线段树维护区间最大最小值，然后线段树上二分即可。

时间复杂度 \Theta((n+q)\log q)。

code