给定一个数组 \(a\),请找一个子序列使得
- \(a_n\) 被选中。
- 相邻两个间距离不超过 \(d\)。
- 比该序列中前面所有数大的数最多。
赛场上考虑了一个 dp,但因为错解想了很久, 没有优化成功。
\(f_i\) 表示从后面到 \(i\) 的最大答案,那么转移的条件就是 \(a_j > a_i\) 且能通过小于 \(a_i\) 的不跳过 \(d\) 得到。这样一来就 \(n^2\) 了。
其实范围可以用并查集的方式处理出来,而因为只可能比其大的产生贡献,所以排个序一次处理就行了。
注意如果相同得把前面的先来,因为是不能等于的转移的。
#include <iostream>
#include <algorithm>
const int N = 300005;
int fa[N], t[N*4], rk[N], a[N], n, d;
void update(int p, int l, int r, int x, int y) {
if (l == r) return t[p] = y, void();
int mid = l + (r-l) / 2;
x <= mid ? update(p+p, l, mid, x, y) : update(p+p+1, mid+1, r, x, y);
t[p] = std::max(t[p+p], t[p+p+1]);
}
int query(int p, int l, int r, int x, int y) {
if (x > y) return 0;
if (l == x && r == y) return t[p];
int mid = l + (r-l) / 2;
if (y <= mid) return query(p+p, l, mid, x, y);
else if (x > mid) return query(p+p+1, mid+1, r, x, y);
else return std::max(query(p+p, l, mid, x, mid),
query(p+p+1, mid+1, r, mid+1, y));
}
int get(int p, int l, int r, int x, int y) {
if (!t[p] || x > y) return 0;
if (l == r) return l;
int mid = l + (r-l) / 2;
if (y <= mid) return get(p+p, l, mid, x, y);
else if (x > mid) return get(p+p+1, mid+1, r, x, y);
else return get(p+p, l, mid, x, mid) ?: get(p+p+1, mid+1, r, mid+1, y);
}
int c(int x) { return std::max(x, 1); }
int find(int x) {
if (fa[x] == x) {
int tmp = get(1, 1, n, c(x-d), x-1);
if (tmp) fa[x] = find(tmp);
return fa[x];
}
return fa[x] = find(fa[x]);
}
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
std::cin >> n >> d;
for (int i = 1; i <= n; i++) std::cin >> a[i], rk[i] = n-i+1;
for (int i = 1; i <= n; i++) fa[i] = i;
std::stable_sort(rk+1, rk+1+n, [&](int x, int y){ return a[x] < a[y]; });
for (int i = 1; i <= n; i++)
update(1, 1, n, rk[i], query(1, 1, n, c(find(rk[i])-d), rk[i]-1)+1);
std::cout << query(1, 1, n, 1, n);
}