强制 \(X_1 < Y_1\)（若不满足，交换 \(X\) 和 \(Y\) 即可）。
把问题抽象为在一个 \(n \times m\) 的 八连通 网格图上，满足 \(X_i \ge Y_j\) 的点 \((i, j)\) 处有障碍，问 \((1, 1)\) 和 \((n, m)\) 是否连通。
不连通的情况分为四种：
- 某一行上全是障碍，即 \(\max\limits_{i = 1}^n X_i \ge \max\limits_{i = 1}^m Y_i\)。
- 某一列上全是障碍，即 \(\min\limits_{i = 1}^m Y_i \le \min\limits_{i = 1}^n X_i\)。
- \((1, 1)\) 被障碍围住，即存在 \((i, j)\)，满足 \(X_i \ge \max\limits_{k = 1}^j Y_k \and Y_j \le \min\limits_{k = 1}^i X_k\)。
- \((n, m)\) 被障碍围住，即存在 \((i, j)\)，满足 \(X_i \ge \max\limits_{k = j}^m Y_k \and Y_j \le \min\limits_{k = i}^n X_k\)。
前两种情况直接判断即可，时间复杂度 \(\mathcal O[q(n + m)]\)，
后两种情况直接做是 \(\mathcal O(qnm)\) 的，显然无法承受。
因为这两种情况是互相对称的，考虑第三种情况即可，第四种情况同理。
枚举 \(i\)，则需要找到最小的满足 \(Y_j \le \min\limits_{k = 1}^i X_k\)（合法）的 \(j\) 来验证 \(X_i \ge \max\limits_{k = 1}^j Y_k\)，观察后不难发现，对于 \(i\) 合法的 \(j\) 和对于 \(i + 1\) 合法的 \(j'\) 间势必满足 \(j \le j'\)，也就是 \(j\) 单调不降，进一步地，第二个循环可以直接丢掉，时间复杂度 \(\mathcal O[q(n + m)]\)。
时间复杂度 \(\mathcal O[q(n + m)]\)。
代码：
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 10;
int n, m, q, x[N], y[N], tx[N], ty[N];
bool flag;
struct Node {
int pre, suf;
void operator=(const int &x) {pre = suf = x;}
} X[N], Y[N];
bool check(const int x[], const int y[]) {
if (x[1] == y[1]) return 0;
else if (x[1] > y[1]) swap(x, y), swap(n, m), flag = 1;
int mx = x[1]; X[1] = x[1], X[n] = x[n];
for (int i = 2; i <= n; i++) mx = max(mx, x[i]), X[i].pre = min(X[i - 1].pre, x[i]);
for (int i = n - 1; i; i--) X[i].suf = min(X[i + 1].suf, x[i]);
int mn = y[1]; Y[1] = y[1], Y[m] = y[m];
for (int i = 2; i <= m; i++) mn = min(mn, y[i]), Y[i].pre = max(Y[i - 1].pre, y[i]);
for (int i = m - 1; i; i--) Y[i].suf = max(Y[i + 1].suf, y[i]);
if (mx >= Y[1].suf || mn <= X[1].suf) return 0;
for (int i = 1, j = 1; i <= n; i++) {
while (j <= m && y[j] > X[i].pre) j++;
if (j == m + 1) break;
if (x[i] >= Y[j].pre) return 0;
}
for (int i = n, j = m; i; i--) {
while (j && y[j] > X[i].suf) j--;
if (!j) break;
if (x[i] >= Y[j].suf) return 0;
}
return 1;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> n >> m >> q;
for (int i = 1; i <= n; i++) cin >> x[i];
for (int i = 1; i <= m; i++) cin >> y[i];
cout << check(x, y);
while (q--) {
if (flag) swap(n, m), flag = 0;
memcpy(tx, x, sizeof(tx)), memcpy(ty, y, sizeof(ty));
int kx, ky, p, v; cin >> kx >> ky;
while (kx--) cin >> p >> v, tx[p] = v;
while (ky--) cin >> p >> v, ty[p] = v;
cout << check(tx, ty);
}
return 0;
}