题意

给定长度为 \(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;
}

JZTXT

[题解] CF474E Pillars

题意

题解