CF1144G Two Merged Sequences

首先我们考虑最暴力的方法，仿照着 LIS 板子题设计状态：\(dp_{i,j}\) 表示考虑前 \(\max(i,j)\) 个，单减序列以 \(i\) 结尾，单增序列以 \(j\) 结尾，然后进行 \(O(1)\) 的转移。

但是这样状态数就爆炸了，如何优化状态数呢？

我们考虑进行换维。因为我们刚刚设计的是一个弱鸡的可行性 DP，很强力的“答案”这个位置上却被我们放上了 \(0/1\) 这样信息很少的东西。

那么就考虑设 \(f_i\) 表示单增序列以 \(i\) 结尾，单减序列最后一项的最大值（浅浅运用贪心的思想，反正只要能分成两个序列就行了，没必要考虑长度的话，只要是已经考虑过的位置，它们之间的相对关系并不重要）。

开始打补丁，因为一个位置也有可能是单减序列的结尾，所以考虑再设一个 \(g\)。

设 \(g_i\) 表示单减序列以 \(i\) 结尾，单增序列最后一项的最小值。那么就可以交替转移了。

转移式子在代码里面。（如果对会不会漏掉情况有疑问，可以这样想：\(f_i,g_i\) 是在考虑前 \(i\) 位时的两个最优情况，其它的情况能匹配的接下来（\(i\) 位之后）的方案，一定能是他们两个交集的子集）。

#include <bits/stdc++.h>

#ifdef LOCAL
#include "zsx.h"
#else 

#endif

using namespace std;

inline char gc() {
	static char buf[100000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
using IO_t = int;inline IO_t read() {
	IO_t x = 0; bool f = 0; char ch = gc();
	while (!isdigit(ch)) {f |= (ch == '-');ch = gc();}
	while (isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ 48);ch = gc();}
	return (f ? -x : x);
}

const int N = 2e5 + 5;

int n , a[N] , f[N] , g[N];

inline bool chkmin(int &x , int y){
	x = x < y ? x : y;
	return x == y;
}
inline bool chkmax(int &x , int y){
	x = x > y ? x : y;
	return x == y;
}

const int INF = 0x3F3F3F3F;

using pii = pair<int , int>;
pii fr[N][2];

int ans[N] , o;
signed main() {
	n = read();
	for(int i = 1; i <= n; ++ i){
		a[i] = read();
	}
	
	f[1] = INF;
	g[1] = -1;
	for(int i = 2; i <= n; ++ i){
		f[i] = -1;
		if(a[i] > a[i - 1]) {
			if(chkmax(f[i] , f[i - 1])){
				fr[i][0] = {i - 1 , 0};
			}
		}
		if(a[i] > g[i - 1]) {
			if(chkmax(f[i] , a[i - 1])){
				fr[i][0] = {i - 1 , 1};
			}
		}
		g[i] = INF;
		if(a[i] < a[i - 1]) {
			if(chkmin(g[i] , g[i - 1])){
				fr[i][1] = {i - 1 , 1};
			}
		}
		if(a[i] < f[i - 1]) {
			if(chkmin(g[i] , a[i - 1])){
				fr[i][1] = {i - 1 , 0};
			}
		}
		if(f[i] == -1 && g[i] == INF){
			puts("NO");
			return 0;
		}
	}
	
	o = n;
	
	puts("YES");
	pii p;
	if(f[n] != -1) p = {n , 0};
	else p = {n , 1};
	while(p.first != 0){
		ans[o -- ] = p.second;
		p = fr[p.first][p.second];
	}
	
	for(int i = 1; i <= n; ++ i){
		printf("%d " , ans[i]);
	}
	
	return 0;
}