题意
给定长度为 \(n\) 的序列 \(a\) 和常数 \(d\)，输出一个最长的 \(a\) 的子序列，使得相邻两项的差的绝对值大于等于 \(d\)。
\(n\le10^5\)
题解
数据结构优化 DP 的板子题了吧。
首先，这道题看上去就很 LIS，我们尝试着用类似 LIS 的思路去做。
设 \(f_i\) 表示以 \(i\) 结尾的符合条件的子序列的最大长度，因为还要输出方案，所以务必再设 \(g_i\) 表示这个方案是从 \(g_i\) 处转移来的。
状态转移方程就很好设了：
\[f_i = \max_{j < i,|a_i - a_j| \ge d}f_j + 1 \]什么都很好处理，除了中间那个绝对值。
所以我们套路的把绝对值拆开，得到：\(a_i - a_j \ge d,a_j - a_i\ge d\)。
我们把 \(a_j\) 单独放在一边，整理得到： \(a_j\le a_i - d,a_j \ge a_i + d\)。
为什么不把 \(a_i\) 单独挑出来？因为后期非常难维护！
我们发现，这个整理得出的式子似乎很好弄？没错，只需要建一棵权值线段树，把每次求完的 \(f_i\) 放到 \(a_i\) 的位置上；查询的时候，我们只要求 \([1,a_i - d] \cup [a_i + d,V]\) 中的最大值即可，其中 \(V\) 是值域。
\(a_i\) 非常大，需要离散化处理一下。
点击查看代码
#include <bits/stdc++.h>
#define P pair<int,int>
using namespace std;
const int N = 1e5 + 5;
int n,d,f[N],g[N];
long long a[N],b[N];
struct Seg{
int l,r;
P dat;
}t[N << 2];
void build(int p,int l,int r){
t[p].l = l, t[p].r = r;
if (l == r) return ;
int mid = (l + r) >> 1;
build(p << 1,l,mid), build(p << 1 | 1,mid + 1,r);
}
void modify(int p,int x,P v){
if (t[p].l == t[p].r) { t[p].dat = max(t[p].dat,v); return ; }
int mid = (t[p].l + t[p].r) >> 1;
if (x <= mid) modify(p << 1,x,v);
else modify(p << 1 | 1,x,v);
t[p].dat = max(t[p << 1].dat,t[p << 1 | 1].dat);
}
P query(int p,int l,int r){
if (l <= t[p].l && t[p].r <= r) return t[p].dat;
int mid = (t[p].l + t[p].r) >> 1; P ma = {0,0};
if (l <= mid) ma = max(ma,query(p << 1,l,r));
if (r > mid) ma = max(ma,query(p << 1 | 1,l,r));
return ma;
}
void print(int x){
if (g[x] == 0){
cout << x << ' ';
return ;
}
print(g[x]);
cout << x << ' ';
}
int main(){
cin >> n >> d;
for (int i = 1;i <= n;i++) cin >> a[i], b[i] = a[i];
sort(b + 1,b + n + 1);
int m = unique(b + 1,b + n + 1) - b - 1;
build(1,1,m);
int ans = 0;
for (int i = 1;i <= n;i++){
int x = lower_bound(b + 1,b + m + 1,a[i]) - b,
l = upper_bound(b + 1,b + m + 1,a[i] - d) - b - 1,
r = lower_bound(b + 1,b + m + 1,a[i] + d) - b;
P res = max({{0,0},query(1,1,l),query(1,r,m)});
f[i] = res.first + 1;
g[i] = res.second;
modify(1,x,{f[i],i});
ans = max(ans,f[i]);
}
cout << ans << '\n';
for (int i = 1;i <= n;i++)
if (f[i] == ans)
return print(i),0;
}