题目
题解
考虑一个计算量 $nm$ 的 DP，设 $f_{i, j}$ 表示能否让 $x_i$ 与 $y_j$ 匹配。转移为
$$f_{i, j} = \left(x_i < y_j\right) \land \left(f_{i - 1, j} \vee f_{i, j - 1} \vee f_{i - 1, j - 1}\right)$$
可以看作在一个 $A_{i, j} = \left[x < y_j\right]$ 的网格上走，问能否从 $\left(1, 1\right)$ 走到 $\left(n, m\right)$。不能走到的话，肯定是因为中间被封死了，有一下四中情况：
- $\exists i, A_{i, *} = 0$
此时要求 $x_i \geq y_*$，即 $\max\limits_{1 \leq k \leq n} x_k \geq \max\limits_{1 \leq k \leq m} y_k$ - $\exists j, A_{*, j} = 0$
此时要求 $x_* \geq y_j$，即 $\min\limits_{1 \leq k \leq n} \geq \min\limits_{1 \leq k \leq m} y_k$ - $\exists \left(i, j\right), A_{i, \leq j} = 0, A_{\leq i, j} = 0$
此时要求 $x_i \geq \max\limits_{1 \leq k \leq j} y_k$ 且 $y_j \leq \min\limits_{1 \leq k \leq i} x_k$。 - $\exists \left(i, j\right), A_{i, \geq j} = 0, A_{\geq i, j} = 0$
此时要求 $x_i \geq \max\limits_{j \leq k \leq m} y_k$ 且 $y_j \leq \min\limits_{i \leq k \leq n} x_k$。
情况 1 和情况 2 容易判断，情况 3 和情况 4 是类似的，我们只讨论情况 3 的处理方法。
我们可以枚举 $i$，我们希望找到一个最小的 $j$，满足 $y_j \leq \min\limits_{1 \leq k \leq i} x_k$，因为更大的 $j$，只会让 $\max\limits_{1 \leq k \leq j} y_k$ 更大，可能使得原本 $x_i \geq \max\limits_{1 \leq k \leq j} y_k$ 的点没有被检测到。我们发现，随着 $i$ 的增大，$j$ 单调不降，于是可以双指针，在 $O\left(n + m\right)$ 的复杂度内判断。
代码
int WITHERING([[maybe_unused]] int TEST_NUMBER) {
tp c, n, m, q; cin >> c >> n >> m >> q;
auto a = vcc(ZERO, n);
auto b = vcc(ZERO, m);
rar(ALL(a));
rar(ALL(b));
auto det = [](vector<tp> x, vector<tp> y) -> bool {
if (x.front() == y.front()) return false;
tp n = x.size();
tp m = y.size();
auto xmn = x;
auto ymx = y;
auto ymn = y;
for (tp i = 1; i < n; ++i) xmn[i] = min(x[i], xmn[i - 1]);
for (tp i = 1; i < m; ++i) ymn[i] = min(y[i], ymn[i - 1]);
for (tp i = 1; i < m; ++i) ymx[i] = max(y[i], ymx[i - 1]);
if (xmn.back() >= ymn.back()) return false;
if (*max_element(ALL(x)) >= ymx.back()) return false;
tp ptr = 0;
for (tp i = 0; i < n; ++i) {
while (ptr + 1 < m && ymn[ptr] > xmn[i]) ++ptr;
if (ymn[ptr] <= xmn[i] && x[i] >= ymx[ptr]) return false;
}
xmn.back() = x.back();
ymn.back() = y.back();
ymx.back() = y.back();
for (tp i = n - 2; i >= 0; --i) xmn[i] = min(x[i], xmn[i + 1]);
for (tp i = m - 2; i >= 0; --i) ymn[i] = min(y[i], ymn[i + 1]);
for (tp i = m - 2; i >= 0; --i) ymx[i] = max(y[i], ymx[i + 1]);
ptr = m - 1;
for (tp i = n - 1; i > 0; --i) {
while (ptr - 1 >= 0 && ymn[ptr] > xmn[i]) --ptr;
if (ymn[ptr] <= xmn[i] && x[i] >= ymx[ptr]) return false;
}
return true;
};
cout << (a.front() < b.front() ? det(a, b) : det(b, a));
while (q--) {
tp ka, kb; cin >> ka >> kb;
auto _a = a;
auto _b = b;
while (ka--) {
tp x, y; cin >> x >> y;
_a[x - 1] = y;
}
while (kb--) {
tp x, y; cin >> x >> y;
_b[x - 1] = y;
}
cout << (_a.front() < _b.front() ? det(_a, _b) : det(_b, _a));
}
cout << '\n';
return 0;
}