自动搬运

查看原文

来自洛谷，原作者为

	w33z8kqrqk8zzzx33 **

搬运于2025-08-24 22:33:14，当前版本为作者最后更新于2021-10-27 22:27:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先，题目描述过于抽象，本质是求 $A$ 的一个子序列，使得这个子序列包含 $A_n$，并且子序列中相邻的元素位置距离 $\le D$，并且从前往后破纪录元素尽量多，求破纪录元素个数。

只有 $A$ 相对顺序有用，所以先将 $A$ 离散化。

考虑 dp，其中 $dp[i]$ 为 $i$ 为破纪录元素时能包含几个破纪录元素。$i$ 肯定为破纪录元素，所以我们需要枚举在 $i$ 前面的第一个破纪录元素 $j$。则 $A_j<A_i$。而为了保证存在一个子序列包含 $i$ 和 $j$，还满足相邻元素距离 $\le D$，必须存在 $j<p_1<p_2<\dots<p_x<i$ 使得

• $p_1-j,p_2-p_1,p_3-p_2,\dots,p_x-p_{x-1},i-p_x\le D$
• $A_{p_1},A_{p_2},\dots,A_{p_k}<A_i$（来保证 $A_i$ 是破纪录元素，注意不需要保证这些小于 $A_j$，因为这样肯定不优）

则可以取所有满足条件的 $j$ 并且求 $dp[i]=\max(dp[j])+1$。直接 dp 可以做到 $O(n^2)$。而发现由于 $i:1\to n$ 时 $A_i$ 的大量变化，维护相邻元素距离约束相对困难，于是考虑对 $A_i$ 扫描线。

按照 $A_i$ 从小到大更新 $dp[i]$，则计算某个 $dp[i]$ 的时候肯定只有已经被更新的 $dp[j]$ 能影响 $dp[i]$。

我们维护一个 set 包含所有已经被更新的位置：这些位置上的值均小于 $A_i$。维护一个并查集，其中 $i$ 和 $j$ 连通当且仅当 $i$ 和 $j$ 被更新并且 $j-i\le D$，则可以从并查集的连通块信息得出任何 $i$ 的最左端 $j$ 使得相邻元素距离约束成立。

然后用并查集得到 $j$ 之后用线段树维护 $dp$ 区间最大值，总共时间复杂度 $O(n\log n)$：

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

#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll = long long;
using pii = pair<int, int>;
//#define int ll
const int MOD = 1000000007;

int las[300005];

int ufs(int u) {
  if (las[u] == -1)
    return u;
  return las[u] = ufs(las[u]);
}
void conn(int u, int v) {
  u = ufs(u), v = ufs(v);
  if (u != v)
    las[max(u, v)] = min(u, v);
}

int seg[300005 << 2];
void upd(int idx, int l, int r, int u, int v) {
  if (!(l <= u && u < r))
    return;
  if (r - l == 1) {
    seg[idx] = v;
    return;
  }
  upd(idx * 2, l, (l + r) / 2, u, v);
  upd(idx * 2 + 1, (l + r) / 2, r, u, v);
  seg[idx] = max(seg[idx * 2], seg[idx * 2 + 1]);
}
int qry(int idx, int l, int r, int L, int R) {
  if (L <= l && r <= R)
    return seg[idx];
  if (R <= l || r <= L)
    return 0;
  return max(qry(idx * 2, l, (l + r) / 2, L, R),
             qry(idx * 2 + 1, (l + r) / 2, r, L, R));
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  memset(las, -1, sizeof las);
  int n, d;
  cin >> n >> d;
  vector<pii> x(n);
  for (int i = 0; i < n; i++)
    cin >> x[i].fi, x[i].se = -i;
  sort(all(x));
  set<int> on;
  int ans = 0;
  for (auto [_, i] : x) {
    i = -i;
    auto pos = on.insert(i).fi;
    if (pos != on.begin() && *pos - *prev(pos) <= d)
      conn(*pos, *prev(pos));
    if (next(pos) != on.end() && *next(pos) - *pos <= d)
      conn(*pos, *next(pos));
    int dp = qry(1, 0, n, ufs(i), i) + 1;
    ans = max(ans, dp);
    upd(1, 0, n, i, dp);
  }
  cout << ans << endl;
}