题解：AT_abc371_f [ABC371F] Takahashi in Narrow Road

wangshulin · 2024-09-16 16:05:21 · 题解

思路

数据结构题。

发现每次移动的总步数等于移动过后的坐标和与移动前的坐标和的差的绝对值，所以需要维护查询区间坐标和。

发现每次坐标的更改又需要维护区间求等差数列。

于是做法就是：每次用二分求出“推箱子”最远会波及哪个人（可以用线段树二分，也可以二分套线段树），求出他们的坐标和，更新答案，然后将这段区间进行等差数列赋值操作即可。

赛时写了 O(n \log^2 n) 的二分套线段树做法，线段树二分可以到 O(n \log n)。

代码

赛时 code。