10/30
23:00
OI

[NOIP2012]开车旅行 [倍增]

开车旅行

考虑一个70分做法:可以发现对于每个人,从每个点出发,下一步到达的地方都是一定的。O(n^2)预处理每个人下一步到达的位置,即可O(n)回答询问。

优化上述两个过程。为了求出在一个点后面,且绝对值差与它小的点,可以使用STL set。O(nlogn)。然后考虑倍增,令f_{x,k}表示x出发,走2^k步到达的位置(显然是轮流走的),g_{x,k,0 / 1}表示A,B分别走过的距离。

可以发现除了k=0,每次都是A开始,B结尾的,因此可以简单倍增处理答案,O(logn)

代码戳这里啦