LibreOJ L2056 「TJOI / HEOI2016」序列

https://loj.ac/p/2056

CDQ 优化 DP 模板？

首先定义对于第 \(x\) 个数其可以变为的最小值为 \(Min_x\)，最大值为 \(Max_x\)，初始为 \(M_x\)。

因为最多只会变一次数，不难想到暴力 DP 的方法：
设 \(dp_i\) 为以 \(i\) 结尾不降子序列的最长长度，可得转移方程：
\(dp_i=\max\{dp_j\}+1(i<j\ \operatorname{and}\ M_j\le Min_i\ \operatorname{and}\ Max_j\le M_i)\)

然后发现这就是个 CDQ 优化 DP 的板子，第一维为 \(i\)，第二维左边为 \(M_i\) 右边为 \(Min_i\)，用树状数组记录前缀最大值更新即可。
CDQ 优化 DP OI - Wiki 指路：https://oi-wiki.org/misc/cdq-divide/#cdq-分治优化-1d1d-动态规划的转移

# include <bits/stdc++.h>
using namespace std;
const int N = 100000;
struct node {
	int id, M, Min, Max, ans;
} a [N + 10], p [N + 10];
int t [N + 10];
int k;
void add (int x, int y) {
	for (int i = x; i <= k; i += i & -i) {
		t [i] = max (t [i], y);
	}
	return ;
}
int query (int x) {
	int ans = 0;
	for (int i = x; i; i -= i & -i) {
		ans = max (ans, t [i]);
	}
	return ans;
}
int use [N + 10];
void clear (int x) {
	for (int i = x; i <= k; i += i & -i) {
		t [i] = 0;
	}
	return ;
}
void CDQ (int l, int r) {
	if (l == r) {
		a [l] .ans = max (a [l] .ans, 1);
		return ;
	}
	int mid = (l + r) >> 1;
	CDQ (l, mid);
	sort (a + l, a + mid + 1, [&] (node x, node y) {
		return x .M < y .M;
	});
	sort (a + mid + 1, a + r + 1, [&] (node x, node y) {
		return x .Min < y .Min;
	});
	int cnt = 0;
	for (int i = l, j = mid + 1; j <= r; ++ j) {
		while (i <= mid && a [i] .M <= a [j] .Min) {
			use [++ cnt] = a [i] .Max;
			add (a [i] .Max, a [i] .ans);// 更新最大值
			++ i;
		}
		a [j] .ans = max (a [j] .ans, query (a [j] .M) + 1);// 查询最大值 + 1
	}
	while (cnt) {
		clear (use [cnt]);
		-- cnt;
	}
	sort (a + mid + 1, a + r + 1, [&] (node x, node y) {
		return x .id < y. id;
	});
	CDQ (mid + 1, r);
	return ;
}
int main () {
	int n, m;
	scanf ("%d %d", & n, & m);
	for (int i = 1; i <= n; ++ i) {
		int x;
		scanf ("%d", & x);
		a [i] .id = i;
		a [i] .M = a [i] .Max = a [i] .Min = x;
		a [i] .ans = 0;
	}
	while (m --) {
		int x, y;
		scanf ("%d %d", & x, & y);
		a [x] .Min = min (a [x] .Min, y);
		a [x] .Max = max (a [x] .Max, y);
	}
	for (int i = 1; i <= n; ++ i) {
		k = max (k, a [i] .Max);
	}
	CDQ (1, n);
	int ans = 0;
	for (int i = 1; i <= n; ++ i) {
		ans = max (ans, a [i] .ans);
	}
	printf ("%d", ans);
	return 0;
}