CF1793F
有一个朴素的想法,使用不删除莫队,使用一种数据结构维护相邻元素的差,\(O(n\sqrt q \log n)\)。
可以通过链表加不增加莫队,维护最小值,使用值域分块,\(O(n\sqrt q+q\sqrt n)\)。
即使如此,也因为常数过大无法通过。
考虑使用扫描线,从右往左扫描区间,将询问挂到左端点上。
大于小于是等价的,先处理大于的。
我们假设现在扫到 \(a_i\),同步记录一个 \(f_j\) 表示 \([i,j]\) 的答案。
先找到右边第一个大于 \(a_i\) 的,设为 \(a_j\),并将 \(j\) 点更新为 \(a_j-a_i\)。
下一步,找下一个 \(a_k\in [a_i,a_j)\),并继续地更新。
这里有一个优化,就是 \(a_k\) 的范围可以调整为 \([a_i,\frac{a_i+a_j}{2}]\),因为在 \([\frac{a_i+a_j}{2},a_j]\) 的势必与 \(a_j\) 更近。
每次范围都减半,保证了复杂度,为 \(O(n\log ^2n +q\log n)\)。
具体地,开一棵值域线段树维护当前值最小的位置,再开一棵线段树维护区间 \(f\) 的值。
这种问题是经典的区间询问问题,允许离线的话,应使用经典的扫描线模型。