代码源NOIP DAY2 T1 LIS和LDS题解

题意

给你两个数组 $a_1,a_2,...,a_n$ 和 $b_1,b_2,...,b_n$。
你需要构造一个 $1$ 到 $n$ 的排列 $p$，满足对于所有 $i$：

• 以第 $i$ 位 结尾 的最长上升子序列长度为 $a_i$。
• 以第 $i$ 位 开头 的最长下降子序列长度为 $b_i$。

数据保证存在一组解。

$1\le n\le 2\times 10^5$。

分析

首先考虑给你一个数组 $p$ 怎样求解最长上升子序列：

有一种做法是 $f_i=\underset{j<i}{\max }{f}_j+1(p_j<p_i)$。

但是这样做对于给定 $f$ 数组（即 $a$ 数组）时，无法确定一些位置之间的大小关系。

另一种做法是我们从前往后求出 $f_i$，假设当前 $f_i=x$，那么我们另外开一个数组 $g_x$ 代表长度为 $x$ 的最长上升子序列的末尾最小值。
那么此时 $g_x$ 数组显然单调递增。因为如果出现了 $g_{x+1}<g_x$，那么我们把 $g_{x+1}$ 所在的长度为 $x+1$ 的最长上升子序列去掉最后一个数，会得到一个长度为 $x$ 的上升子序列。而这个子序列的末尾元素一定比 $g_x$ 要小。
那么每次求 $f_i$ 就可以在 $g$ 数组上二分最后一个小于 $p_i$ 的位置，然后就把 $g_{f_i}$ 更新成 $p_i$。

能够这样更新的原因是 $p_i$ 一定比原来的 $g_{f_i}$ 更小。因为如果更大的话 $f_i$ 可以接上前面一个长度为 $f_i$ 的子序列，那么 $f_i$ 的值应该等于 $f_i+1$，与条件矛盾。

那么如果我们知道了最终的 $f$ 数组，可以按照上述过程得到一些数的大小关系。例如一个 $f_i=2$ 的位置 $i$ 上面的数应该 大于之前最靠后的 $f_{i^{\prime }}=1$ 的位置 $i^{\prime }$ 上的数，小于之前最靠后的 $f_{i^{\prime \prime }}=2$ 的位置 $i^{\prime \prime }$ 上的数。

那么我们可以用一条 有向边 来表示这样的大小关系。可以连一条 $i^{\prime }$ 指向 $i$ 的有向边和一条 $i$ 指向 $i^{\prime \prime }$ 的有向边。

并且这样的 大小关系限制 是 $f_i$ 数组的形态的 充要条件。

只要能够满足这样的大小限制，就一定能得到 $f$ 数组。对于本题而言，根据 $a_i$ 我们可以连出一些有向边。根据 $b_i$ 也可以连出一些有向边。我们把图建出来跑一遍拓扑排序即可。

具体的连边方式，以下只说明 $a_i$， $b_i$ 只需要倒着扫描数组即可：

1. 连一条 $ls{t}_{a_i-1}$ 指向 $i$ 的有向边。连一条 $i$ 指向 $ls{t}_{a_i}$ 的有向边。
2. 将 $ls{t}_{a_i}$ 更新为 $i$。

拓扑排序每次拿出的队头位置 $p$，令 $p$ 上的数为还没填的最小数即可。
时间复杂度 $O(n)$。

CODE：

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int N = 2e5 + 10;
int n, a[N], b[N];
int lst[N];
int in[N];
vector< int > E[N];
int ans[N], rk;
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
	for(int i = 1; i <= n; i ++ ) {
		int o = lst[a[i] - 1];
		int p = lst[a[i]];
		if(o) {
			E[o].pb(i);
			in[i] ++;
		}
		if(p) {
			E[i].pb(p);
			in[p] ++;
		}
		lst[a[i]] = i;
	}
	memset(lst, 0, sizeof lst);
	for(int i = n; i >= 1; i -- ) {
		int o = lst[b[i] - 1];
		int p = lst[b[i]];
		if(o) {
			E[o].pb(i);
			in[i] ++;
		}
		if(p) {
			E[i].pb(p);
			in[p] ++;
		}
		lst[b[i]] = i;
	}
	queue< int > q;
	for(int i = 1; i <= n; i ++ ) {
		if(in[i] == 0) q.push(i);
	}
	while(!q.empty()) {
		int u = q.front(); q.pop();
		ans[u] = ++ rk;
		for(auto v : E[u]) {
			in[v] --;
			if(!in[v]) q.push(v);
		}
	}
	for(int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
	return 0;
}