题解：P14231 复读机 / repeat

2024 NOIP 联考供题，数据范围略有加强。

给你一个长度为 $n$ 的序列 $a_{1\dots n}$。

接下来有 $q$ 次查询，每次给出一个区间 $[l,r]$ 和 $k$，你需要在区间中选择一个长为 $k$ 的子序列，最小化相邻两项的和的最大值。

$n,q\le 3\times10^5$。

对于一个数 $v$，取出最长的相邻两项和 $\le v$ 的子序列，如果其长度 $\ge k$ 那么答案就 $\le v$。

我们把 $2a_i\le v$ 的数称为「小数」，反之称之为「大数」。小数必定可连选，大数必定不可连选。

最优情况必定为小数全选，对于每相邻两个小数，如果它们之间最小的大数可选就选上。

那么我们按值域从小到大做扫描线，每次会将一些大数切换为小数。注意到相邻的小数之间显然均为大数，所以可以求出若干四元组 $(i,j,l,r)$ 表示在 $v\in [l,r]$ 时 $i,j$ 为相邻小数且对答案有 $1$ 的贡献。差分为对 $v\ge l$ 的单点加矩形求和，还需注意 $[i,j]$ 跨过端点时的贡献。

对这些四元组以及询问进行整体二分即可。

时间复杂度 $O((n+q)\log^2n)$。

继续优化，发现对于一个时刻 $v$，仍有贡献的四元组 $(i,j,l,r),l\le v\le r$ 的区间 $[i,j]$ 除端点外互不相交，那么数点可以降一维：只要求 $i$ 在区间内，此时只会算多包含右端点的一个贡献区间。

前驱后继可以类似地在整体二分中双指针维护。

时间复杂度 $O((n+q)\log n)$。