自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:44:16，当前版本为作者最后更新于2023-02-09 17:52:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很不错的题目，思路很自然，结论较难证但好猜，思维含量很高。

首先二分答案转化为 $01$ 序列，目标是将所有数全部变成 $1$。

基本性质：若可操作 $I_1, I_2$ 且 $I_1\subset I_2$，则操作 $I_2$ 一定更优。

设最优操作序列为 $I_1, I_2, \cdots, I_e$。

设 $1$ 的权值为 $1$，$0$ 的权值为 $-1$，前缀和序列为 $s$，每次可将权值为正的一段区间全部变成 $1$。设操作 $I$ 时其权值为 $v(I)$。

性质 1：对于 $1\leq i < e$，$v(I_i) = 1$。

证明：设 $v(I_i) > 1$，则 $I_i$ 向左或向右扩展 $1$ 一定不会使得 $v(I_i)\leq 0$。

$\square$

性质 1 的推论：

• 设操作 $I$ 时区间内原有 $1$ 的数量为 $o(I)$，消去 $0$ 的数量为 $z(I)$，若 $I\neq [1, n]$，则 $o(I) = z(I) + 1$，进一步有 $|I| = o(I) + z(I) = 2o(I) - 1$。

性质 2：若存在方案使得 $[1, n]$ 全为 $1$，则 $e\leq \lceil \log_2 n\rceil$。

证明：若初始存在 $o(I) \geq 2$ 且 $v(I) > 0$，即存在 $101$ 或 $11$ 作为子串，则总存在操作序列，使得 $o(I_{i + 1}) \geq |I_i| = 2o(I_i) - 1$，易知 $o(I_i) \geq 2 ^ {i - 1} + 1$，则 $e\leq \lceil \log_2 n\rceil$。

若初始不存在这样的 $I$，即无法操作长度大于 $1$ 的区间，则无法对序列产生任何影响，即无解。

$\square$

性质 3：对于任意 $1\leq i < j \leq e$，$I_i\subseteq I_j$ 或 $I_j \subseteq I_i$。

证明：

先证明 相交必然包含：考虑两次相交但不包含的操作 $I_i = [a, c]$，$I_j = [b, d]$，其中 $a < b \leq c < d$，则令 $I_j = [a, d]$ 一定合法，因为此时 $[a, b)$ 均为 $1$。

接下来只需证明 一定相交。我们使用调整法。

找到最后两个相邻且不交的区间 $I_j, I_{j + 1}$，则 $I_{j + 1}\subset I_{j + 2} \subset \cdots \subset I_e$。因为 $I_e = [1, n]$，所以存在 $j + 1\leq p < e$ 使得 $I_p\cup I_j = \varnothing$，且 $I_{p + 1} \cup I_j = I_j$。

若 $|I_j| \geq |I_p|$，我们可以将 $I_{j + 1}\sim I_p$ 全部取消，替换为 $I_j$ 的 “超区间” $I_j\subset I\subseteq I_{p + 1}$，这样消去 $0$ 的数量为 $|I_j| - 1\geq |I_p| - 1$，而 $I_{j + 1}\sim I_p$ 消去的 $0$ 的数量显然不超过 $|I_p| - 2$，所以替换后 $I_{p + 1}$ 的权值一定增加，而操作数不增。

若 $|I_j| < |I_p|$，类似地，取消操作 $I_j$，替换为在 $I_p$ 后插入 $I_p$ 的 “超区间” $I_p\subset I\subseteq I_{p + 1}$，$I_{p + 1}$ 的权值增加，而操作数不变。

调整后，相邻且不交的区间的位置单调递减，因此调整总可以结束。

$\square$

有了性质 2 和性质 3，我们可以设计 DP $f_{i, l, r}$ 表示 $I_i = [l, r]$ 是否可行。转移暴力枚举扩展区间，单次检查时间复杂度 $\mathcal{O}(n ^ 4\log n)$。

根据基本性质，对于每个 $l$，我们只关心最大的 $r$ 使得 $f_{i, l, r} = 1$。因此，考虑 值域定义域互换 的套路，设 $f_{i, l}$ 表示从 $l$ 开始，最大的 $r$ 使得原 $f_{i, l, r}$ 等于 $1$。

再根据基本性质，如果 $p < q$ 且 $f_{i, p} \geq f_{i, q}$，那么 $f_{i, q}$ 是无用的。因此，从 $f_{i - 1} \to f_i$ 时，我们只关心所有不被包含的 $I_l = [l, f_{i - 1, l}]$ 区间，即左右端点单调递增。

设 $c(I)$ 表示操作 $I = [l, r]$ 后相对于原序列，对包含 $I$ 的区间的权值产生的贡献，即 $r - l + 1 - (s_r - s_{l - 1})$。考虑检查 $f_{i, l}$ 能否为 $p$，那么我们求出所有使得 $[j, f_{i - 1, j}]\subseteq [l, p]$ 的 $c([j, f_{i - 1, j}])$ 的最大值 $c_{\max}$，那么 $s_p - s_{l - 1}$ 加上 $c_{\max}$ 之后应为正数，即 $s_{l - 1} - c_{\max} < s_p$。

这样，我们有了单次检查 $\mathcal{O}(n ^ 2\log n)$ 的做法。结合递增性质，换成扫描线 + 单调栈 + 线段树二分即可 $\mathcal{O}(n\log ^ 2 n)$，但总复杂度 $\mathcal{O}(n \log ^ 3 n)$ 及大常数仍无法通过。

我们进一步利用递增性质，从后往前扫描线。加入区间 $I_l$ 时，权值小于 $c(I_l)$ 的区间就无用了。这启发我们使用单调队列，从队头到队尾 区间位置从右往左，同时 权值递减。我们希望找到队列中的第一个位置 $I_p$，使得存在 $q \geq f_{i - 1, p}$ 且 $s_{l - 1} - c(I_p) < s_q$。预处理 $g_i$ 表示使得 $s_q \geq i$ 的最大的 $q$，则相当于检查是否有 $g(s_{l - 1} - c(I_p) + 1)\geq f_{i - 1, p}$。

$g$ 显然具有单调性，$-c(I_p) + 1$ 同样单调增（$c(I_p)$ 递减），问题在于 $s_{l - 1}$。但是我们也有方法解决：$p < q$ 且 $s_p \leq s_q$，则 $q$ 肯定不会作为左端点，丢掉所有这样的位置之后，$s_{l - 1}$ 随着 $l$ 递减而单调递增，故 $s_{l - 1} - c(I_p) + 1$ 递增，可使用单调队列维护。

看了下标算，定义是相同的，换了一种转移方式：求值的极值而不是求位置的极值。感觉麻烦了点。

总时间复杂度 $\mathcal{O}(n\log ^ 2 n)$。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 4e5 + 5;
int n, k, a[N], b[N], s[N];
int f[N], tag[N], buc[N << 1];
bool check(int x) {
  for(int i = 1; i <= n; i++) {
    s[i] = s[i - 1] + (a[i] >= x ? 1 : -1);
  }
  memset(tag, 0, sizeof(tag));
  for(int i = 1, lim = N; i <= n; i++) {
    if(s[i - 1] < lim) lim = s[i - 1], tag[i] = 1;
  }
  memset(buc, 0, n + 2 << 3);
  for(int i = 1; i <= n; i++) buc[n + s[i]] = i;
  for(int i = n * 2 - 1; ~i; i--) buc[i] = max(buc[i], buc[i + 1]);
  for(int i = 1; i <= n; i++) f[i] = i - 1;
  for(int _ = 1; _ <= k && (1 << _ - 1) <= n; _++) {
    static int d[N], val[N], hd, tl;
    hd = 1, tl = 0;
    for(int i = n; i; i--) {
      if(!tag[i]) continue;
      int v = f[i] - i + 1 - (s[f[i]] - s[i - 1]);
      while(hd <= tl && v >= val[tl]) tl--;
      val[++tl] = v, d[tl] = f[i];
      while(hd <= tl) {
        int v = val[hd], p = buc[max(0, s[i - 1] + 1 - v + n)];
        if(p >= d[hd]) {f[i] = p; break;}
        hd++;
      }
    }
    if(f[1] == n) return _ <= k;
  }
  return 0;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
  sort(b + 1, b + n + 1);
  int c = unique(b + 1, b + n + 1) - b - 1;
  int l = 1, r = c;
  while(l < r) {
    int m = l + r + 2 >> 1;
    if(check(b[m])) l = m;
    else r = m - 1;
  }
  cout << b[l] << "\n";
  return 0;
}