问题分析

这是一个经典的最长不下降子序列（LIS）问题的变体，允许在序列中进行最多 $K$ 次区间加操作。关键在于如何利用这些操作来最大化保留的玉米数量。

关键观察

1. 拔高操作的性质：每次拔高操作选择一个区间，将该区间内所有玉米高度增加 $1$。为了最大化序列的不下降性，最优策略通常是对后缀进行拔高操作。

2. 动态规划状态设计：定义 $dp[i][j]$ 表示以第 $i$ 株玉米结尾，且进行了 $j$ 次拔高操作时的最长不下降子序列长度。

3. 状态转移：对于每个玉米 $i$ 和可能的操作次数 $j$，我们需要找到所有 $k < i$ 且满足 $a[k] + l \leq a[i] + j$ 的 $dp[k][l]$ 的最大值，其中 $l \leq j$。

算法优化

直接枚举所有可能的 $k$ 和 $l$ 会导致 $O(N^2 \cdot K^2)$ 的时间复杂度，无法接受。因此需要使用数据结构优化：

1. 二维树状数组/线段树：维护一个二维数据结构，其中第一维是玉米的高度 $a[i] + j$，第二维是操作次数 $j$。这样可以在 $O(\log N \cdot \log K)$ 时间内完成查询和更新操作。

2. 查询优化：对于每个状态 $dp[i][j]$，查询所有满足 $a[k] + l \leq a[i] + j$ 且 $l \leq j$ 的 $dp[k][l]$ 的最大值。

3. 更新策略：计算完 $dp[i][j]$ 后，更新数据结构中位置 $(a[i] + j, j)$ 的值。

复杂度分析

• 时间复杂度：$O(N \cdot K \cdot \log H \cdot \log K)$，其中 $H$ 是玉米的最大高度。
• 空间复杂度：$O(H \cdot K)$，可以通过优化数据结构降低空间使用。

代码实现

#include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
  vector<int> tree;
  int n;
  void init(int _n) {
    n = _n;
    tree.assign(4 * (n + 1), 0);
  }
  void update(int pos, int val) {
    update_util(1, 1, n, pos, val);
  }
  void update_util(int node, int start, int end, int pos, int val) {
    if (start == end) {
      tree[node] = val;
      return;
    }
    int mid = (start + end) / 2;
    if (pos <= mid)
      update_util(node * 2, start, mid, pos, val);
    else
      update_util(node * 2 + 1, mid + 1, end, pos, val);
    tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
  }
  int query(int left, int right) {
    if (left > right) return 0;
    return query_util(1, 1, n, left, right);
  }
  int query_util(int node, int start, int end, int left, int right) {
    if (right < start || left > end) return 0;
    if (left <= start && end <= right) return tree[node];
    int mid = (start + end) / 2;
    return max(query_util(node * 2, start, mid, left, right),
               query_util(node * 2 + 1, mid + 1, end, left, right));
  }
};

struct FenwickMax {
  vector<int> tree;
  FenwickMax(int _n) : tree(_n + 1, 0) {}
  void update(int pos, int val) {
    int n = tree.size() - 1;
    while (pos <= n) {
      tree[pos] = max(tree[pos], val);
      pos += pos & -pos;
    }
  }
  int query(int pos) {
    int res = 0;
    while (pos > 0) {
      res = max(res, tree[pos]);
      pos -= pos & -pos;
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (int &x : A) cin >> x;
  const int MAXH = 5005;
  const int MAXS = MAXH + K + 5;
  const int MAXDD = K + 5;
  vector<FenwickMax> height_trees(K + 1, FenwickMax(5000));
  vector<vector<int>> height_vals(K + 1, vector<int>(5001, 0));
  vector<SegmentTree> diag_trees(MAXS);
  for (auto &st : diag_trees) st.init(MAXDD);
  auto get_pmin = [&](int s) { return max(1, s - K); };
  auto get_pmax = [&](int s) { return min(5000, s); };
  auto get_idx = [&](int s, int p) {
    int pmin = get_pmin(s);
    int pmax = get_pmax(s);
    if (p < pmin || p > pmax) return -1;
    return p - pmin + 1;
  };
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int curr = A[i];
    vector<int> newl(K + 1, 1);
    for (int ck = 0; ck <= K; ck++) {
      int case1 = 0;
      if (curr >= 1) case1 = height_trees[ck].query(curr);
      int case2 = 0;
      int s = curr + ck;
      if (s >= 0 && s < MAXS) {
        int pl = curr + 1;
        int pr = get_pmax(s);
        if (pl <= pr) {
          int idxl = get_idx(s, pl);
          int idxr = get_idx(s, pr);
          if (idxl != -1 && idxl <= idxr) {
            case2 = diag_trees[s].query(idxl, idxr);
          }
        }
      }
      int pre = max(case1, case2);
      newl[ck] = 1 + pre;
    }
    for (int ck = 1; ck <= K; ck++) {
      newl[ck] = max(newl[ck], newl[ck - 1]);
    }
    ans = max(ans, *max_element(newl.begin(), newl.end()));
    for (int ck = 0; ck <= K; ck++) {
      int oldv = height_vals[ck][curr];
      int updv = max(oldv, newl[ck]);
      height_vals[ck][curr] = updv;
      height_trees[ck].update(curr, updv);
      int s = curr + ck;
      if (s >= 0 && s < MAXS) {
        int idx = get_idx(s, curr);
        if (idx != -1) {
          int oldd = diag_trees[s].query(idx, idx);
          int updd = max(oldd, newl[ck]);
          diag_trees[s].update(idx, updd);
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}