CF1539E Game with Cards()

把最终答案看成一段 \(0\), 一段 \(1\) 的一个串。
如果说我们的答案中有一段 \(0\) (\(1\) 同理)。
那么所有 \(0\) 的数都满足所有第一个范围,这段 \(0\) 前面的 \(1\) 代表数满足所有的第二个范围。
然后呢,因为我一个数改变了之后只要满足后面的条件与前面无关,所以我们不妨从后往前倒着处理,不断缩小条件范围。
扫的过程中,维护第二个范围的区间,扫到一个位置看第二个条件行不行,转移一下即可,并且要保证第一个条件始终满足。
正确性的话,我们能转移就转移,可以保证连续的 \(0\) 或 \(1\) 的段长度最小,对于第一个条件无所谓,但可以保证对于第二个条件更优。
Tips:
如果操作只对后面有影响可以考虑倒着做。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 1e5 + 10;
int n, m, mn[2], l[N][2], r[N][2], L[2], R[2], a[N], fir[2], both[2], nxt[N][2];

int main(){
	//FO("");
	read(n, m);
	mn[1] = mn[0] = n + 1, fir[0] = fir[1] = 1, L[0] = L[1] = 0, R[1] = R[0] = m;

	U(i, 1, n)
		read(a[i], l[i][0], r[i][0], l[i][1], r[i][1]);

	D(i, n, 1) {
		U(j, 0, 1) if (a[i] >= l[i][j] && a[i] <= r[i][j]) 
			fir[j] &= 1; else fir[j] &= 0;
		
		U(j, 0, 1) 
			chkmax(L[j], l[i][j]), chkmin(R[j], r[i][j]);
		
		U(j, 0, 1)
			if (fir[j] && a[i - 1] >= L[j ^ 1] && a[i - 1] <= R[j ^ 1]) 
				both[j] = 1;
			else both[j] = 0;
		U(j, 0, 1)
			if (both[j]) nxt[i][j] = mn[j ^ 1];

		U(j, 0, 1)
			if (both[j]) mn[j] = i, fir[j ^ 1] = 1, L[j] = 0, R[j] = m;
	}

	if (mn[0] > 1 && mn[1] > 1) {
		puts("No");
		return 0;
	}
	puts("Yes");
	int cur = 0;
	if (mn[0] > 1) cur = 1;
	for (int i = 1; i <= n; i = nxt[i][cur], cur ^= 1) {
		U(j, i, nxt[i][cur] - 1) writesp(cur);
	}
	return 0;
}
————————

把最终答案看成一段 \(0\), 一段 \(1\) 的一个串。
如果说我们的答案中有一段 \(0\) (\(1\) 同理)。
那么所有 \(0\) 的数都满足所有第一个范围,这段 \(0\) 前面的 \(1\) 代表数满足所有的第二个范围。
然后呢,因为我一个数改变了之后只要满足后面的条件与前面无关,所以我们不妨从后往前倒着处理,不断缩小条件范围。
扫的过程中,维护第二个范围的区间,扫到一个位置看第二个条件行不行,转移一下即可,并且要保证第一个条件始终满足。
正确性的话,我们能转移就转移,可以保证连续的 \(0\) 或 \(1\) 的段长度最小,对于第一个条件无所谓,但可以保证对于第二个条件更优。
Tips:
如果操作只对后面有影响可以考虑倒着做。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 1e5 + 10;
int n, m, mn[2], l[N][2], r[N][2], L[2], R[2], a[N], fir[2], both[2], nxt[N][2];

int main(){
	//FO("");
	read(n, m);
	mn[1] = mn[0] = n + 1, fir[0] = fir[1] = 1, L[0] = L[1] = 0, R[1] = R[0] = m;

	U(i, 1, n)
		read(a[i], l[i][0], r[i][0], l[i][1], r[i][1]);

	D(i, n, 1) {
		U(j, 0, 1) if (a[i] >= l[i][j] && a[i] <= r[i][j]) 
			fir[j] &= 1; else fir[j] &= 0;
		
		U(j, 0, 1) 
			chkmax(L[j], l[i][j]), chkmin(R[j], r[i][j]);
		
		U(j, 0, 1)
			if (fir[j] && a[i - 1] >= L[j ^ 1] && a[i - 1] <= R[j ^ 1]) 
				both[j] = 1;
			else both[j] = 0;
		U(j, 0, 1)
			if (both[j]) nxt[i][j] = mn[j ^ 1];

		U(j, 0, 1)
			if (both[j]) mn[j] = i, fir[j ^ 1] = 1, L[j] = 0, R[j] = m;
	}

	if (mn[0] > 1 && mn[1] > 1) {
		puts("No");
		return 0;
	}
	puts("Yes");
	int cur = 0;
	if (mn[0] > 1) cur = 1;
	for (int i = 1; i <= n; i = nxt[i][cur], cur ^= 1) {
		U(j, i, nxt[i][cur] - 1) writesp(cur);
	}
	return 0;
}