一道题

· · 个人记录

题意：给定一个序列 a 和一个空序列 b，依次扫 a 中每一个元素，可以放在 b 序列此时的头或者尾。使最终 b 数组相邻两个元素差的最大值最小。要求 O(n\log V)，V 是值域。

【两只 log 写法】

AC 的基石。

将问题转化为：将原序列分成2个子序列，一个以 a_1 开头，一个以 a_2 开头，最小化子序列中相邻元素差的最大值。

首先二分答案 x，将 (a_i,a_{i+1}) 属于不同的子序列的位置称为分界位置，记为 (i,i+1)。

考虑一个分界位置 (i,i+1) 是合法的，当且仅当存在分界位置 (j,j+1)，满足：

  2. |a_j-a_{i+1}|\le x

  3. 子串 a_{j+1}\sim a_i 中不存在相差超过 x 的相邻元素。

考虑从小到大枚举 i，去找它之前的 j。

对于条件2，注意到满足条件的 a_j 的值是一段区间。

对于条件3，满足条件的 j 是一段以 i-1 为右端点的区间，并且可以用倍增求出。 我们只需要知道最大的满足条件1、2的 j 中最大的那个是否在这个区间里即可。

因此，我们用下线段树维护合法的分界位置，支持查询 a_j 在某一段区间中的 j 的最大值即可。

时间复杂度 O(n\log n\log V)，常数比较大。

【正解：一只 log】

还是二分，考虑维护 b 的两侧可放数的集合。

放入前两个数，两侧集合是 [a_1-x,a_1+x],[a_2-x,a_2+x]。

接下来如果一个数只能放在一边，容易维护。

如果两边都放不了，此次二分无解。

否则就是两个区间都能放。这种情况的难点其实是后面有需要的时候，我们可能会把这种数移到另一边去。

但其实有一个巧妙的操作：假设 a_3 两边可放，我们选择放到左边，则右边的可放数的集合会变成 [a_1-x,a_1+x]\cup[a_2-x,a_2+x]！

为什么呢？想想如果我们来了一个数 w\not\in [a_3-x,a_3+x] 但是 w\in [a_1-x,a_1+x]，我们把 w 放到右边，实际是等价于把 a_3 放到右边，w 放到左边！而且这样做之后两边的区间是 [a_3-x,a_3+x],[w-x,w+x]，和正常做是一样的！

可能有问题：如果 [a_1-x,a_1+x]\cup[a_2-x,a_2+x] 不是区间怎么办？但这是不可能的，因为进入这种情况要求 a_3 两边可放，所以必有交，它们的并也还是一个区间。

于是就维护两个区间即可。