夏晓光(loveJY)的博客

忘了原题题号了QAQ

https://acm.nflsoj.com/problem/442

这是个加强版,带上了个系数,做法可能有所不同

查询$i,j \in [l,r]min|a_i-a_j|$

然后考虑怎么做,可以利用值域减半原理

我们尝试处理出每个点i的最优点对(i,j),即能在i,j区间作为i的最优答案的数对

首先我们对于i,i-1可以算出一个最近点对,然后考虑能不能作为目标更新下一个

首先你要发现i-1肯定也按照我们的原则处理出了一些最近点对....

那么也就是说下一个更靠前的j要作为答案,当且仅当不能和i-1成为最优而和i成为最优

也就是说$a_j$离$a_i$而不是$a_{i-1}$更近

于是乎就可以发现这样的$a_j<|a_{i-1}-a_{i}|/2+a_{i}$

那么你会发现这个值域减少了一半

所以我们对于i最多会有logX个最优点对

全局一共有nlogX个

那么对于所有询问可以离线到右端点上

然后每次到点i时把点i所形成的最优点对以左端点为下标放入到线段树上,相当于扫描线

你会发现答案就是一个区间查询最小值

时间复杂度$O(nlog_2nlog_2X)$实际可以跑不满