题意简述
有 \(n\) 个广告，每个广告在一个时间段内占据二维平面的矩形，\(m\) 个约束表示两个广告至少有一个要被选择，选择若干广告，满足所有约束且同时刻不能有重叠的广告。
Kosaraju 算法流程
- 在正图上跑一遍 DFS，给每个位置打上时间戳
- 从时间戳大到小枚举点，在反图上跑 DFS，这个时候对于一个起点，他能搜到的所有点就和他在同一个强连通分量里。
思路
考虑 2-SAT，可以 \(O(n^2)\) 建边跑 Tarjan，算法瓶颈在于建边，注意到数据范围用 bitset 刚好可以，考虑用 bitset 维护偏序关系，具体而言预处理每一个偏序维度的前后缀 bitset，表示哪些广告满足这个不等式，然后对于一个广告，在三个维度上用前后缀 bitset 与出来所有和它有交的广告就行了。
这样实现了 \(O(\dfrac{n^2}{\omega})\) 建图，然而边数依旧是 \(O(n^2)\) 的，无论如何 Tarjan 都跑不动，考虑使用 Kosaraju 算法求 SCC。
这个算法的好处是只需要跑朴素的 DFS 就可以完成缩点，所以不断使用 _Find_first() 函数就可以找到一个点出发的所有未被访问节点，因为一个点只会被访问一次，所以总复杂度是 \(O(\dfrac{n^2}{\omega})\)。
码来
// Copyright © 2024 Moyou
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <bitset>
//#define int long long
using namespace std;
const int N = 50005, M = 4005;
int n, m, w, h, l[N], r[N], x[N], y[N], edn[N << 1], timestamp, id[N << 1];
bitset<N> g[N], pre1[M], pre2[M], pre3[M], suf1[M], suf2[M], suf3[M], ok[2];
vector<int> G[N];
bool check(int x) {return x > n ? ok[1].test(x - n) : ok[0].test(x);}
int idi(int x) {return x > n ? x - n : x + n;}
void kosaraju1(int u) {
ok[u > n].reset(u > n ? u - n : u);
if(u <= n) {
g[u] &= ok[1];
for(int v = g[u]._Find_first(); g[u].any(); v = g[u]._Find_first()) {
kosaraju1(v + n);
g[u] &= ok[1];
}
}
else {
for(auto v : G[u - n])
if(check(v))
kosaraju1(v);
}
edn[++ timestamp] = u;
}
void kosaraju2(int u) {
id[u] = timestamp;
ok[u > n].reset(u > n ? u - n : u);
if(u <= n) {
for(auto v : G[u])
if(check(v + n))
kosaraju2(v + n);
}
else {
g[u - n] &= ok[0];
for(int v = g[u - n]._Find_first(); g[u - n].any(); v = g[u - n]._Find_first()) {
kosaraju2(v);
g[u - n] &= ok[0];
}
}
}
inline char get_char() {
static char buf[1 << 16], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 16, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
int x = 0, f = 1;
char ch = get_char();
while (!isalnum(ch)) (ch == '-' ? f = -1 : 1), ch = get_char();
while (isalnum(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = get_char();
return x * f;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) write(x / 10);
putchar(x % 10 + '0');
return;
}
signed main() {
n = read(), w = read(), h = read();
for(int i = 1; i <= n; i ++) {
l[i] = read(), r[i] = read(), x[i] = read(), y[i] = read();
pre1[l[i]].set(i), suf1[r[i]].set(i), pre2[x[i]].set(i), suf2[x[i] + w - 1].set(i), pre3[y[i]].set(i), suf3[y[i] + h - 1].set(i);
}
for(int i = 1; i < M; i ++) pre1[i] |= pre1[i - 1], pre2[i] |= pre2[i - 1], pre3[i] |= pre3[i - 1];
for(int i = M - 2; i; i --) suf1[i] |= suf1[i + 1], suf2[i] |= suf2[i + 1], suf3[i] |= suf3[i + 1];
for(int i = 1; i <= n; i ++)
g[i] = suf1[l[i]] & pre1[r[i]] & suf2[x[i]] & pre2[x[i] + w - 1] & suf3[y[i]] & pre3[y[i] + h - 1], g[i].reset(i);
m = read();
for(int i = 1, a, b; i <= m; i ++)
a = read(), b = read(), G[a].push_back(b), G[b].push_back(a);
ok[0].set(), ok[1].set();
for(int i = 1; i <= n * 2; i ++) if(check(i)) kosaraju1(i);
timestamp = 0;
ok[0].set(), ok[1].set();
for(int i = 1; i <= n; i ++)
g[i] = suf1[l[i]] & pre1[r[i]] & suf2[x[i]] & pre2[x[i] + w - 1] & suf3[y[i]] & pre3[y[i] + h - 1], g[i].reset(i);
for(int i = n * 2; i; i --) if(check(edn[i])) timestamp ++, kosaraju2(edn[i]);
for(int i = 1; i <= n; i ++) if(id[i] == id[i + n]) return puts("No"), 0;
puts("Yes");
for(int i = 1; i <= n; i ++) {
if(id[i] < id[n + i]) putchar('0');
else putchar('1');
}
return 0;
}