自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 21:56:25，当前版本为作者最后更新于2018-12-10 21:29:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意简述：

给定一个长度为 $n$ 的序列 $a$。

同时这个序列还可能发生变化，每一种变化 $(x_i,y_i)$ 对应着 $a_{x_i}$ 可能变成 $y_i$。

不会同时发生两种变化。

需要找出一个最长的子序列，使得这个子序列在任意一种变化下都是不降的。

只需要求出这个子序列的长度即可。

注意：可以不发生任何变化。

题解：

记 $f[i]$ 为以第 $i$ 项结尾的子序列最长长度。

则有转移：$f[i]=\max_{j<i}(f[j])+1$，同时还要满足 $maxval_j\le a_i$ 和 $a_j\le minval_i$。
其中 $maxval_i$ 表示第 $i$ 项最大能变成的值，$minval_i$ 表示第 $i$ 项最小能变成的值。

按照项从小到大转移，形成了天然的时间顺序，同时还要满足两个偏序限制。

算上时间顺序，这是一个三维偏序问题，用 CDQ 分治 + 数据结构（我用了树状数组）就能解决。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MN = 100005;
const int MC = 100000;

int N, M;
int A[MN], Mx[MN], Mn[MN];
int f[MN], Ans;
int p[MN];
inline bool cmp1(int i, int j) { return Mx[i] < Mx[j]; }
inline bool cmp2(int i, int j) { return A[i] < A[j]; }

int B[MN];
inline void Ins(int i, int x) { for (; i <= MC; i += i & -i) B[i] = max(B[i], x); }
inline void Clr(int i) { for (; i <= MC; i += i & -i) B[i] = 0; }
inline int Qur(int i) { int A = 0; for (; i; i -= i & -i) A = max(A, B[i]); return A;}

void CDQ(int lb, int rb) {
	if (lb == rb) {
		f[lb] = max(f[lb], 1);
		return;
	}
	int mid = lb + rb >> 1;
	CDQ(lb, mid);
	for (int i = lb; i <= rb; ++i)
		p[i] = i;
	sort(p + lb, p + mid + 1, cmp1);
	sort(p + mid + 1, p + rb + 1, cmp2);
	int j = lb;
	for (int i = mid + 1; i <= rb; ++i) {
		while (j <= mid && Mx[p[j]] <= A[p[i]]) {
			Ins(A[p[j]], f[p[j]]);
			++j;
		}
		f[p[i]] = max(f[p[i]], Qur(Mn[p[i]]) + 1);
	}
	for (int i = lb; i <= mid; ++i)
		Clr(A[i]);
	CDQ(mid + 1, rb);
}

int main() {
	int x, y;
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &A[i]),
		Mx[i] = Mn[i] = A[i];
	for (int i = 1; i <= M; ++i)
		scanf("%d%d", &x, &y),
		Mx[x] = max(Mx[x], y),
		Mn[x] = min(Mn[x], y);
	CDQ(1, N);
	for (int i = 1; i <= N; ++i)
		Ans = max(Ans, f[i]);
	printf("%d\n", Ans);
	return 0;
}