题解：AT_abc389_f [ABC389F] Rated Range

· · 题解

贴一下赛时做法。

先说一些符合直觉的性质：

  1. 答案是关于初始位置单调不降的；
  2. 在二维平面上，不同位置出发的轨迹折线不会在除了结束位置以外的地方相交。

我们考虑对初始位置扫描线，然后维护轨迹穿过了哪些比赛对应的区间，那么不难得到一个推论就是对于一场比赛穿过区间的轨迹对应的初始位置是连续的一段。

也就是说对于一场比赛出现 穿过到不穿过 或者 不穿过到穿过 这种变化各最多只有一次。

那我们就考虑在扫描线过程中维护这些变化，假设折线在第 i 场比赛位于 pos，那我们可以用 l_i-pos 或者 r_i+1-pos 来刻画，实现上就是找第一个非正数，线段树二分即可。

然后对于找到的比赛 i 对轨迹在 [i+1,n] 进行区间加一或者减一即可。

复杂度是均摊 O(n\log n+V+q)，应该是目前理论复杂度最优。

submission