首先 \(x_1 = y_1\) 显然不合法。若 \(x_1 > y_1\) 就把 \(x, y\) 全部取相反数，这样就只用考虑 \(x_1 < y_1\) 的情况了。
然后考虑一个 \(O(nmq)\) 的 dp，设 \(f_{i, j}\) 为拓展 \(X\) 的前 \(i\) 个元素和 \(Y\) 的前 \(j\) 个元素是否可行。那么若 \(x_i < y_j\) 则 \(f_{i, j}\) 取 \(f_{i - 1, j}, f_{i, j - 1}, f_{i - 1, j - 1}\) 的或，否则 \(f_{i, j} = 0\)。
发现这个 dp 的转移形式很像网格上行走，于是考虑转成网格上的问题。考虑令 \(c_{i, j} = [x_i < y_j]\)，那么可行当且仅当能找到一条从 \((1, 1)\) 到 \((n, m)\) 的全为 \(1\) 的八连通的路径。
注意到任意两行之间 \(1\) 的位置总是包含关系，这意味着不用考虑斜着走，即 \((i - 1, j - 1)\) 走到 \((i, j)\)，因为可以被 \((i - 1, j - 1) \to (i - 1, j) \to (i, j)\) 或 \((i - 1, j - 1) \to (i, j - 1) \to (i, j)\) 的其中一个代替。于是只用考虑四连通的路径。
考虑从特殊性质入手，即网格第 \(n\) 行和第 \(m\) 列全为 \(1\)（如果不全为 \(1\) 一定不可行），这样只要到达第 \(n\) 行或第 \(m\) 列就赢了。考虑递归求解，设 \(f(n, m)\) 为当前在 \((1, 1)\)，是否能到达第 \(n\) 行或第 \(m\) 列。设 \(i = \operatorname{argmin}_{k = 1}^{n - 1}\{x_k\}, j = \operatorname{argmax}_{k = 1}^{m - 1}\{y_k\}\)。若第 \(i\) 列全为 \(1\) 则可以直接递归至 \(f(i, m)\)，若第 \(j\) 列全为 \(1\) 则可以直接递归至 \(f(n, j)\)；若都不满足，则网格一定存在一个以 \(0\) 组成的十字架，把起点和终点隔开，于是这种情况直接返回不可行。所有要用到的信息都能预处理 \(x, y\) 的前缀 \(\text{minmax}\) 数组然后 \(O(1)\) 求出，所以复杂度为 \(O((n + m)q)\)。
对于一般的情况，考虑设 \(u = \operatorname{argmin}_{k = 1}^n\{x_k\}, v = \operatorname{argmax}_{k = 1}^m\{y_k\}\)，那么第 \(u\) 行和第 \(v\) 列一定要全为 \(1\)。容易发现网格被第 \(u\) 行和第 \(v\) 列分成了左上角和右下角两个互相独立的部分，于是把右下角的部分翻转过来，做一遍同样的问题即可。
总时间复杂度就是 \(O((n + m)q)\)。
code
#include <bits/stdc++.h>
#define fst first
#define scd second
#define pb emplace_back
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
typedef long double ldb;
inline int read() {
int x = 0;
bool f = 0;
char c = getchar();
while (c < '0' || c > '9') {
f |= (c == '-');
c = getchar();
}
while ('0' <= c && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return f ? -x : x;
}
const int maxn = 500100;
const int inf = 0x3f3f3f3f;
int n, m, q, test, a[maxn], b[maxn];
int c[maxn], d[maxn];
pii pcmn[maxn], pcmx[maxn], pdmn[maxn], pdmx[maxn];
pii scmn[maxn], scmx[maxn], sdmn[maxn], sdmx[maxn];
int dfs1(int x, int y) {
if (x == 1 || y == 1) {
return 1;
}
int p1 = pcmn[x - 1].scd, p2 = pdmx[y - 1].scd;
if (c[p1] < pdmn[y - 1].fst) {
return dfs1(p1, y);
} else if (pcmx[x - 1].fst < d[p2]) {
return dfs1(x, p2);
} else {
return 0;
}
}
int dfs2(int x, int y) {
if (x == n || y == m) {
return 1;
}
int p1 = scmn[x + 1].scd, p2 = sdmx[y + 1].scd;
if (c[p1] < sdmn[y + 1].fst) {
return dfs2(p1, y);
} else if (scmx[x + 1].fst < d[p2]) {
return dfs2(x, p2);
} else {
return 0;
}
}
inline int calc() {
if (c[1] == d[1]) {
return 0;
}
if (c[1] > d[1]) {
for (int i = 1; i <= n; ++i) {
c[i] = -c[i];
}
for (int i = 1; i <= m; ++i) {
d[i] = -d[i];
}
}
pcmn[0].fst = pdmn[0].fst = inf;
pcmx[0].fst = pdmx[0].fst = -inf;
for (int i = 1; i <= n; ++i) {
pcmn[i] = min(pcmn[i - 1], mkp(c[i], i));
pcmx[i] = max(pcmx[i - 1], mkp(c[i], i));
}
for (int i = 1; i <= m; ++i) {
pdmn[i] = min(pdmn[i - 1], mkp(d[i], i));
pdmx[i] = max(pdmx[i - 1], mkp(d[i], i));
}
scmn[n + 1].fst = inf;
sdmn[m + 1].fst = inf;
scmx[n + 1].fst = -inf;
sdmx[m + 1].fst = -inf;
for (int i = n; i; --i) {
scmn[i] = min(scmn[i + 1], mkp(c[i], i));
scmx[i] = max(scmx[i + 1], mkp(c[i], i));
}
for (int i = m; i; --i) {
sdmn[i] = min(sdmn[i + 1], mkp(d[i], i));
sdmx[i] = max(sdmx[i + 1], mkp(d[i], i));
}
int p1 = pcmn[n].scd, p2 = pdmx[m].scd;
for (int i = 1; i <= m; ++i) {
if (c[p1] >= d[i]) {
return 0;
}
}
for (int i = 1; i <= n; ++i) {
if (c[i] >= d[p2]) {
return 0;
}
}
return dfs1(p1, p2) && dfs2(p1, p2);
}
void solve() {
test = read();
n = read();
m = read();
q = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
}
for (int i = 1; i <= m; ++i) {
b[i] = read();
}
for (int i = 1; i <= n; ++i) {
c[i] = a[i];
}
for (int i = 1; i <= m; ++i) {
d[i] = b[i];
}
putchar('0' + calc());
while (q--) {
for (int i = 1; i <= n; ++i) {
c[i] = a[i];
}
for (int i = 1; i <= m; ++i) {
d[i] = b[i];
}
int kx, ky;
kx = read();
ky = read();
while (kx--) {
int x, y;
x = read();
y = read();
c[x] = y;
}
while (ky--) {
int x, y;
x = read();
y = read();
d[x] = y;
}
putchar('0' + calc());
}
putchar('\n');
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
有小丑场上把
for (int i = 1; i <= n; ++i) {
c[i] = a[i];
}
for (int i = 1; i <= m; ++i) {
d[i] = b[i];
}
写成了
for (int i = 1; i <= n; ++i) {
c[i] = a[i];
d[i] = b[i];
}
暴挂 \(30\) 分，怎么会是呢。