思路与算法

按首元素大小统一为X<Y；相等立即失败。合法拓展等价于在格点(i,j)中沿右/下方向从(1,1)到(n,m)找始终X_i<Y_j的路径。允许同时推进的对角线可拆为至少一个合法中间格；路径长至多n+m-1，再重复最后一对补到10^100。 必要条件minX<minY、maxX<maxY保证全局最小X行和最大Y列完全合法，构成中心枢纽。剩下障碍是前缀L：存在i,j使X_i≥max(Y_1..Y_j)，且Y_j≤min(X_1..X_i)。同样检查反向数组的前缀L。存在任一障碍则失败，否则可连通枢纽。 线性查前缀L：随i前进维护X的前缀最小值，指针j指向首个Y_j≤此前缀最小值的位置，j只前进；维护经过的Y最大值，若X_i达到或超过此最大值即有障碍。正反各扫一次。每个额外询问从原数组临时修改、判定、再恢复，询问相互独立。

正确性说明

对角两端严格合法时，若两个中间格都非法，则有X_i<Y_j≤X_(i+1)<Y_(j+1)≤X_i矛盾，故路径化等价。全局极值条件恰排除完全阻塞的行列。前缀L两臂分别封住前缀矩形的下边和右边，任何从起点向中心枢纽的路径必越其一，故必要。 充分性可沿已到达的前缀最小X行和最大Y列扩展：只在刷新最小值时换行、刷新最大值时换列，其间整段均严格合法。若不能继续扩展到枢纽，则第一条挡住的行满足X_i≥当前前缀最大Y，第一条挡住的列满足Y_j≤当前前缀最小X，恰组成上述L，矛盾。故无前缀L可从起点到枢纽，反向无L可从枢纽到终点。最小X行与最大Y列交叉，拼接合法。扫描中j选首个满足第二式的列；后续列的前缀最大值只更大，故若首个列不能形成L，其余也不能，判据完整。

复杂度

初始化原数组O(n+m)，每个状态做常数趟线性扫描O(n+m)，修改恢复共O(总修改数)。总时间O((q+1)(n+m)+总修改数)，空间O(n+m+单次修改数)。n,m≤500000、q≤60的实际GNU满规模通过原1秒限制。

易错点

严格不等号不能允许相等；必须正反两侧都查。询问之间不可累积修改。原站10100按CCF原卷文字的上标扁平化现象及公开同源10^{100}还原，属于明确记录的排版推断，原始HTML保留，不声称实际看过PDF公式像素。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
bool prefixClear(const vector<int> &x, const vector<int> &y, bool reversed) {
    int n = x.size(), m = y.size(), j = 0, minX = 1000000000, maxY = -1;
    auto Y = [&](int z) {
        return y[reversed ? m - 1 - z : z];
    };
    for (int i = 0; i < n; i++) {
        int a = x[reversed ? n - 1 - i : i];
        minX = min(minX, a);
        while (j < m && Y(j) > minX) {
            maxY = max(maxY, Y(j));
            ++j;
        }
        if (j == m)
            return true;
        maxY = max(maxY, Y(j));
        if (a >= maxY)
            return false;
    }
    return true;
}
bool solve(const vector<int> &A, const vector<int> &B) {
    if (A[0] == B[0])
        return false;
    const vector<int> &x = A[0] < B[0] ? A : B;
    const vector<int> &y = A[0] < B[0] ? B : A;
    auto xx = minmax_element(x.begin(), x.end()), yy = minmax_element(y.begin(), y.end());
    if (*xx.first >= *yy.first || *xx.second >= *yy.second)
        return false;
    return prefixClear(x, y, false) && prefixClear(x, y, true);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int c, n, m, q;
    cin >> c >> n >> m >> q;
    vector<int> a(n), b(m);
    for (int &v : a)
        cin >> v;
    for (int &v : b)
        cin >> v;
    cout << solve(a, b);
    while (q--) {
        int kx, ky;
        cin >> kx >> ky;
        vector<pair<int, int>> saveA, saveB;
        for (int i = 0, p, v; i < kx; i++) {
            cin >> p >> v;
            --p;
            saveA.push_back({p, a[p]});
            a[p] = v;
        }
        for (int i = 0, p, v; i < ky; i++) {
            cin >> p >> v;
            --p;
            saveB.push_back({p, b[p]});
            b[p] = v;
        }
        cout << solve(a, b);
        for (auto p : saveA)
            a[p.first] = p.second;
        for (auto p : saveB)
            b[p.first] = p.second;
    }
    cout << '\n';
}