CF765F Souvenirs

题意：给出一个长度为 的序列 。

次询问一个区间内差值最小的对子。

，，时限。

---

考虑扫描线：向右逐步移动右端点，维护每个左端点对应的答案。

为了方便我们只考虑顺序对的答案，将值域取反重做即可得到正确答案。

当在右侧加入数 时：

对于前面的某个数 若 则数对 可以对区间 产生贡献。

考虑 的某个数 ， 比 更优的条件 。

与此同时，考虑到 的贡献，还有 。

化简可得 。

综上可得必要条件 。

不难发现，每次产生可能有效的 ，都会使得这个区间减半。

查询第一个满足条件的 等价于如下问题：值域区间内的位置前继。

可以使用主席树维护。

总复杂度 。