题解：P14231 复读机 / repeat

· · 题解

\text{Link}

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

题意

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

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

## 题解 对于一个数 $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)$。