令$s_{r}(i)$表示题面中的$s(i,r)$

注意到,对于一个$r$,$s_{r}(i)$不会超过$\sqrt m$种

从左到右枚举$r$,线段树维护$s_{r}$,然后再在线段树上$dfs$计算以$r$右端点的答案,就是当一个区间的$s_{r}(i)$一样时直接$check$一下区间左端点然后返回.

具体怎么维护线段树,就是枚举到$i$的时候

先令$s_{i}=s_{i-1}$,然后对于每个$j$,$s_{i}(1..j)$都对$abs(a_{i}-a_{j})$取$min$

但实际上有可能更新的$j$只有$log(m)$个

因为考虑$a_{j}>a_{i}$的情况,假设所有可能的$j$从大到小是$j_{1..m}$,则有$2 (a_{j_{k+1}}-a_{i}) < a_{j_{k}}-a_{i}$.

时间$O(nlog^2)+O(n \sqrt m log \frac{n}{\sqrt m} ))$

后面这个东西虽然带$log$但常数比较小(把线段树换成平衡树好像就不带$log$了)

代码:http://uoj.ac/submission/264123