这题的一个log做法

kczno1 2018-05-23 19:19:14 2018-05-23 20:13:44

考虑对每个询问二分答案
如果询问坐标为 x ,答案 \ge m 等价于存在一种店在 (x-m,x+m) 不存在店,等价于在 [x+m,inf) 存在店前驱 \le x-m
对每种店开个 set ,对全局开个线段树维护区间最小前驱即可两个 log
在线段树上二分即可一个 log

具体说一下。
你要求的是最大的 i ,满足 记 [i,inf) 的最小前驱为 mn ,则 mn+i \le 2 \times x
无解的情况先特判掉。
假如你现在在线段树上的 [l,r]
如果 x 落在 [mid+1,r] ,那么 i 一定落在 [mid+1,r]
如果 x 落在 [1,mid] ,那么你需要判断最终的答案会不会落在 [mid+1,r] 上。
由于 i 越小, mn 越小,所以你只用检查一下 mid+1 是否满足 mn+i \le 2 \times x 即可。

代码 https://loj.ac/submission/109219

共 1 条回复

soaring

写得好