「THUPC 2023 初赛」喵了个喵 II

「THUPC 2023 初赛」喵了个喵 II

Problem

给定一个长为 \(4n\) 的序列，其中 \(1∼n\) 各出现 \(4\) 次。问是否能够将其划分为两个相等的子序列。

Thinking

既然是2-SAT，从2入手

考虑每个数只出现两次

令每个数出现的两个位置为 \(l,r\)

手玩数据发现有解的条件应该是任意一个 \([l,r]\) 不相交

假如相交了，像这样: 1 2 2 1

发现顺序相反，就不可能构造出解

Solution

考虑将4个的情况化为2个的情况

即拆成 \(x1,x2,x3,x4 \to [x1,x2],[x3,x4]|[x1,x3],[x2,x4]\)

现在就有了两种选择情况，考虑快速维护区间包含关系

暴力连边建图复杂度平方无法接受，考虑线段树优化建图

扫描线+线段树的话不便于连边的撤销

于是这里使用主席树快速回退版本

先按照 \(r\) 排序

分治线段树 \(l,r\) 间的点进行连边，再把 \(l\) 加入主席树新版本

Code

稠密图推荐链前，洛谷vector会TLE

#include <bits/stdc++.h>
using namespace std;
inline int read() {int x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9') {if(!(ch ^ '-')) f = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}return x * f;}
inline void write(int x) {if(x < 0) {putchar('-');x = -x;}if(x > 9) {write(x / 10);} putchar(x % 10 + '0');}
const int N = 200010, M = N * 20, V = (N + M) * 2;
int n, ap[N][5], tot = 0, cnt = 0, tr[M], ls[M], rs[M], rt[M], dfn[V], low[V], ttot = 0, scc[V], scc_cnt = 0, ans[N << 2];
vector <int> e[V];
struct line {int l, r, pos;} l[N * 4];
void ade(int u, int v) {e[u].emplace_back(v), e[v ^ 1].emplace_back(u ^ 1);}
void insertN(int q, int &p, int l, int r, int x, int id) {
	p = ++cnt, tr[p] = tot, ls[p] = ls[q], rs[p] = rs[q];
	if (tr[q]) ade(tr[p], tr[q]); tot += 2;
	if (l == r) return ade(tr[p], id), void();
	int mid = l + r >> 1;
	x <= mid ? insertN(ls[q], ls[p], l, mid, x, id) : insertN(rs[q], rs[p], mid + 1, r, x, id);
	if (ls[p]) ade(tr[p], tr[ls[p]]); if (rs[p]) ade(tr[p], tr[rs[p]]);
}	
void insert(int p, int l, int r, int ql, int qr, int id) {
	if (!p) return;
	if (ql <= l && r <= qr) return ade(id, tr[p]), void();
	int mid = l + r >> 1;
	if (ql <= mid) insert(ls[p], l, mid, ql, qr, id);
	if (mid < qr) insert(rs[p], mid + 1, r, ql, qr, id);
}
stack <int> sta; bool insta[V];
void tarjan(int u) {
	low[u] = dfn[u] = ++ttot, sta.emplace(u), insta[u] = 1;
	for (auto v : e[u])
		if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
		else if (insta[v]) low[u] = min(low[u], dfn[v]);
	if (low[u] == dfn[u]) {
		int v; scc_cnt++;
		do v = sta.top(), sta.pop(), insta[v] = 0, scc[v] = scc_cnt; while (v != u);
	}
}
int main() {
	n = read();
	for (int a, i = 1; i <= n << 2; i++) a = read(), ap[a][++ap[a][0]] = i;
	int tail = 0;
	for (int i = 1; i <= n; i++)
        l[++tail] = {ap[i][1], ap[i][2], tot}, l[++tail] = {ap[i][3], ap[i][4], tot},
        l[++tail] = {ap[i][1], ap[i][3], tot ^ 1}, l[++tail] = {ap[i][2], ap[i][4], tot ^ 1}, tot += 2;
	sort (l + 1, l + tail + 1, [&] (const line x, const line y) {return x.r < y.r;});
    tr[0] = tot, tot += 2;
    for (int i = 1; i <= n << 2; i++)
		insert(rt[i - 1], 1, n << 2, l[i].l, l[i].r, l[i].pos), insertN(rt[i - 1], rt[i], 1, n << 2, l[i].l, l[i].pos ^ 1);
	for (int i = 0; i < tot; i++) if (!dfn[i]) tarjan(i);
	for (int i = 0; i < tot; i++) if (scc[i] == scc[i ^ 1]) return cout << "No", 0;
	cout << "Yes\n";
	for (int i = 1; i <= tail; i++) if (scc[l[i].pos] < scc[l[i].pos ^ 1]) ans[l[i].l] = 0, ans[l[i].r] = 1;
	for (int i = 1; i <= n << 2; i++) write(ans[i]);
	return 0;
}