思路与算法

正序放棋会把3类道路的空格连通块拆开，不便维护；倒序移走棋子则只会合并空格。先将所有询问的棋子放上，再按q到1移走当前棋子。移走i并处理完后，棋盘恰为第i次落子之前；将当前位置当作出发点，统计可到达的其他格子。 每个3路空格并查集分量维护四棵可合并动态线段树：行主序位置、列主序位置，以及黑白两色的边界棋集合。先把行列减1，行主序编号为x·m+y，列主序为y·n+x。空格树叶值为1；边界棋按(等级,落子编号)排序的唯一键编号，叶值也只为0或1。同一棋子从多条3路接触同一分量仍只记一次，合并叶子时取逻辑或。颜色分树后，对异色树作等级前缀计数就得到3路可吃的棋数。 倒序移走一枚棋时，为新空格建立位置树，合并所有3路空邻居分量，把它周围尚占据的3路邻居加入边界集合，并从合并后的边界集合删除刚移走棋子的唯一键。这样3路贡献就是分量大小减1，再加异色且等级不高于当前棋的边界棋数。 2路不能转弯。预处理每格横、竖方向连续2路段的两端；用两个有序集合维护行主序、列主序的占据位置。对出发点求前驱后继，截出被最近棋子挡住的空区间。横向用行位置树查询该区间已经属于3路分量的空格数，竖向用列位置树查询，区间长度减去此数就是新增贡献。最近阻挡棋若位于连续2路范围内、可吃且不在3路边界集合中，再加1。最后直接检查1路邻格：空格若已在3路分量就跳过，棋子若已在3路边界可吃集合也跳过。按原询问次序输出。

正确性说明

倒序状态不变量：处理完i后，尚占据的位置恰为编号小于i的棋，所有空格按3路连通关系构成并查集分量；每个分量的两棵位置树恰含它的全部空格，边界树恰含与它至少有一条3路相接的尚占据棋，每枚棋至多一次。初始化直接建立所有最终空格、合并3路空边并收集占据邻棋，满足不变量。移走i时，只新增当前空点和与它相接的空边，故合并空邻居完整刻画新连通块。原边界的并集再加入当前点的占据邻居，正好是新边界；i已为空且其所有空邻分量都已合并，删除它的键即可。其他分量不受影响。因此不变量归纳成立。 3路移动不能穿过占据格，全部可达空格正是含起点分量中除起点外的格子。所有可吃终点恰为异色、等级合格的边界棋；合并时叶取布尔或，保证多处接触同一棋也只计一个物理位置。 2路的每个方向必须沿同一行或列的连续2边行进，并在第一个占据格处终止。预处理段端点和占据前驱后继的截断恰给出全部可走空格；位置树范围计数恰删除其中已由3路到达的格子，起点包含在区间和位置树中，二者相减也自动去掉起点。横竖区间除起点外不交，故不会互相重复；横竖阻挡棋也不可能是同一格。1路只有邻格一步，若能同时由2路直行到达这个相邻格，就必须让同一条边同时为1和2，矛盾，因此1路与2路之间无需扣重，剩下只需按上述集合检查它与3路的重叠。所有贡献对应合法单次移动，且覆盖所有允许的道路类型，故总数正确。

复杂度

记N=n·m。读图、预处理四个2路端点与初始化并查集O(N)，排序等级和建立占据有序集合O(Qlog Q)。每个格子只在变空时向两棵位置树各插入一次。某枚棋的边界插入只可能来自与它相接的至多4条3路边，每条边在另一端变空时贡献一次，因此全部边界插入次数不超过4Q。每次点操作O(log N)，总开点数至多(2N+4Q)(ceil(log₂N)+1)+1。 线段树合并中，每次两个非空树结点相遇都会让其中一个结点退出活结构，退出结点不再重新出现，所以全部合并总访问量由总开点数线性界定。每个询问常数次范围计数、边界键查询和占据前驱后继操作，均O(log N)。总时间O((N+Q)log N)，空间O((N+Q)log N)。满N=200000、Q=100000时预留15200001个三整数结点，节点池约174MiB；其余位置、并查集、等级、有序集合仍为线性空间。节点池一次reserve，避免扩容时旧新数组同时驻留。

易错点

不能混用不同道路，也不能在吃子后继续行进。边界按唯一落子编号而非只按等级去重，同级不同棋必须分别计数；同一棋多处接触则只计一次。逆序删除当前棋的边界键不可遗漏，否则会留下已不存在的棋。纵向区间要在列主序中查询，行主序不能直接表达一列的连续区间。2路最近棋子即使不可吃也会挡路，不能继续找下一枚。起点不是合法目标。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int left = 0, right = 0, sum = 0;
};
struct SegmentPool {
    int n;
    vector<Node> tree;
    SegmentPool(int count, int q) : n(count) {
        int depth = 0;
        while ((1 << depth) < n)
            depth++;
        tree.reserve((2ULL * n + 4ULL * q) * (depth + 1) + 1);
        tree.push_back(Node());
    }
    int change(int root, int left, int right, int position, int value) {
        if (!root) {
            if (!value)
                return 0;
            root = tree.size();
            tree.push_back(Node());
        }
        if (left == right) {
            tree[root].sum = value;
            return root;
        }
        int middle = (left + right) / 2;
        if (position <= middle) {
            int child = change(tree[root].left, left, middle, position, value);
            tree[root].left = child;
        } else {
            int child = change(tree[root].right, middle + 1, right, position, value);
            tree[root].right = child;
        }
        tree[root].sum = tree[tree[root].left].sum + tree[tree[root].right].sum;
        return root;
    }
    int merge(int a, int b, int left, int right) {
        if (!a || !tree[a].sum)
            return b;
        if (!b || !tree[b].sum)
            return a;
        if (left == right) {
            tree[a].sum = 1;
            return a;
        }
        int middle = (left + right) / 2;
        int l = merge(tree[a].left, tree[b].left, left, middle);
        int r = merge(tree[a].right, tree[b].right, middle + 1, right);
        tree[a].left = l;
        tree[a].right = r;
        tree[a].sum = tree[l].sum + tree[r].sum;
        return a;
    }
    int query(int root, int left, int right, int low, int high) const {
        if (!root || !tree[root].sum || low > high)
            return 0;
        if (low <= left && right <= high)
            return tree[root].sum;
        int middle = (left + right) / 2, answer = 0;
        if (low <= middle)
            answer += query(tree[root].left, left, middle, low, high);
        if (high > middle)
            answer += query(tree[root].right, middle + 1, right, low, high);
        return answer;
    }
    bool contains(int root, int position) const {
        int left = 0, right = n - 1;
        while (root && tree[root].sum && left < right) {
            int middle = (left + right) / 2;
            if (position <= middle) {
                root = tree[root].left;
                right = middle;
            } else {
                root = tree[root].right;
                left = middle + 1;
            }
        }
        return root && tree[root].sum;
    }
    int change(int root, int position, int value) {
        return change(root, 0, n - 1, position, value);
    }
    int merge(int a, int b) {
        return merge(a, b, 0, n - 1);
    }
    int query(int root, int low, int high) const {
        return query(root, 0, n - 1, low, high);
    }
};
struct Board {
    int n, m, q, N;
    vector<unsigned char> horizontal, vertical;
    vector<int> occupied, color, level, position, key, levelCut;
    vector<int> parent, size, rowTree, columnTree;
    vector<array<int, 2>> boundary;
    vector<int> horizontalLeft, horizontalRight, verticalTop, verticalBottom;
    unique_ptr<SegmentPool> pool;
    set<int> rowOccupied, columnOccupied;
    int find(int u) {
        int r = u;
        while (parent[r] != r)
            r = parent[r];
        while (parent[u] != u) {
            int next = parent[u];
            parent[u] = r;
            u = next;
        }
        return r;
    }
    int unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return u;
        if (size[u] < size[v])
            swap(u, v);
        parent[v] = u;
        size[u] += size[v];
        rowTree[u] = pool->merge(rowTree[u], rowTree[v]);
        columnTree[u] = pool->merge(columnTree[u], columnTree[v]);
        for (int c = 0; c < 2; c++)
            boundary[u][c] = pool->merge(boundary[u][c], boundary[v][c]);
        return u;
    }
    int columnIndex(int u) const {
        return (u % m) * n + u / m;
    }
    int rowIndex(int v) const {
        return (v % n) * m + v / n;
    }
    template <class F> void neighbors(int u, F f) const {
        int row = u / m, col = u % m;
        if (col + 1 < m)
            f(u + 1, horizontal[u]);
        if (col)
            f(u - 1, horizontal[u - 1]);
        if (row + 1 < n)
            f(u + m, vertical[u]);
        if (row)
            f(u - m, vertical[u - m]);
    }
    void read() {
        cin >> n >> m >> q;
        N = n * m;
        horizontal.assign(N, 0);
        vertical.assign(N, 0);
        string s;
        for (int x = 0; x < n; x++) {
            cin >> s;
            for (int y = 0; y < m - 1; y++)
                horizontal[x * m + y] = s[y] - '0';
        }
        for (int x = 0; x < n - 1; x++) {
            cin >> s;
            for (int y = 0; y < m; y++)
                vertical[x * m + y] = s[y] - '0';
        }
        occupied.assign(N, 0);
        color.resize(q + 1);
        level.resize(q + 1);
        position.resize(q + 1);
        key.resize(q + 1);
        levelCut.resize(q + 1);
        vector<pair<int, int>> order(q);
        for (int i = 1, x, y; i <= q; i++) {
            cin >> color[i] >> level[i] >> x >> y;
            --x;
            --y;
            position[i] = x * m + y;
            occupied[position[i]] = i;
            order[i - 1] = {level[i], i};
            rowOccupied.insert(position[i]);
            columnOccupied.insert(columnIndex(position[i]));
        }
        sort(order.begin(), order.end());
        vector<int> sortedLevel(q);
        for (int j = 0; j < q; j++) {
            key[order[j].second] = j;
            sortedLevel[j] = order[j].first;
        }
        for (int i = 1; i <= q; i++)
            levelCut[i] = upper_bound(sortedLevel.begin(), sortedLevel.end(), level[i]) -
                          sortedLevel.begin() - 1;
        horizontalLeft.resize(N);
        horizontalRight.resize(N);
        verticalTop.resize(N);
        verticalBottom.resize(N);
        for (int u = 0; u < N; u++) {
            horizontalLeft[u] = (u % m && horizontal[u - 1] == 2) ? horizontalLeft[u - 1] : u;
            verticalTop[u] = (u >= m && vertical[u - m] == 2) ? verticalTop[u - m] : columnIndex(u);
        }
        for (int u = N - 1; u >= 0; u--) {
            horizontalRight[u] = (u % m + 1 < m && horizontal[u] == 2) ? horizontalRight[u + 1] : u;
            verticalBottom[u] =
                (u + m < N && vertical[u] == 2) ? verticalBottom[u + m] : columnIndex(u);
        }
        parent.resize(N);
        iota(parent.begin(), parent.end(), 0);
        size.assign(N, 0);
        rowTree.assign(N, 0);
        columnTree.assign(N, 0);
        boundary.resize(N);
        pool.reset(new SegmentPool(N, q));
        for (int u = 0; u < N; u++)
            if (!occupied[u]) {
                size[u] = 1;
                rowTree[u] = pool->change(0, u, 1);
                columnTree[u] = pool->change(0, columnIndex(u), 1);
            }
        for (int u = 0; u < N; u++)
            if (!occupied[u]) {
                if (u % m + 1 < m && horizontal[u] == 3 && !occupied[u + 1])
                    unite(u, u + 1);
                if (u + m < N && vertical[u] == 3 && !occupied[u + m])
                    unite(u, u + m);
            }
        for (int u = 0; u < N; u++)
            if (occupied[u]) {
                int piece = occupied[u];
                neighbors(u, [&](int v, int kind) {
                    if (kind == 3 && !occupied[v]) {
                        int root = find(v);
                        boundary[root][color[piece]] =
                            pool->change(boundary[root][color[piece]], key[piece], 1);
                    }
                });
            }
    }
    vector<int> solve() {
        vector<int> answer(q);
        for (int i = q; i >= 1; i--) {
            int u = position[i], column = columnIndex(u);
            occupied[u] = 0;
            parent[u] = u;
            size[u] = 1;
            rowTree[u] = pool->change(0, u, 1);
            columnTree[u] = pool->change(0, column, 1);
            boundary[u] = {0, 0};
            neighbors(u, [&](int v, int kind) {
                if (kind == 3 && !occupied[v])
                    unite(u, v);
            });
            int root = find(u);
            neighbors(u, [&](int v, int kind) {
                if (kind == 3 && occupied[v]) {
                    int piece = occupied[v];
                    boundary[root][color[piece]] =
                        pool->change(boundary[root][color[piece]], key[piece], 1);
                }
            });
            boundary[root][color[i]] = pool->change(boundary[root][color[i]], key[i], 0);
            rowOccupied.erase(u);
            columnOccupied.erase(column);
            int opposite = color[i] ^ 1;
            int result = size[root] - 1 + pool->query(boundary[root][opposite], 0, levelCut[i]);
            auto capture = [&](int v) {
                int piece = occupied[v];
                return piece && color[piece] != color[i] && level[piece] <= level[i] &&
                       !pool->contains(boundary[root][opposite], key[piece]);
            };
            int left = -1, right = N;
            auto it = rowOccupied.lower_bound(u);
            if (it != rowOccupied.end())
                right = *it;
            if (it != rowOccupied.begin())
                left = *prev(it);
            int low = max(horizontalLeft[u], left + 1), high = min(horizontalRight[u], right - 1);
            result += high - low + 1 - pool->query(rowTree[root], low, high);
            if (left >= horizontalLeft[u] && capture(left))
                ++result;
            if (right <= horizontalRight[u] && capture(right))
                ++result;
            left = -1;
            right = N;
            it = columnOccupied.lower_bound(column);
            if (it != columnOccupied.end())
                right = *it;
            if (it != columnOccupied.begin())
                left = *prev(it);
            low = max(verticalTop[u], left + 1);
            high = min(verticalBottom[u], right - 1);
            result += high - low + 1 - pool->query(columnTree[root], low, high);
            if (left >= verticalTop[u] && capture(rowIndex(left)))
                ++result;
            if (right <= verticalBottom[u] && capture(rowIndex(right)))
                ++result;
            neighbors(u, [&](int v, int kind) {
                if (kind != 1)
                    return;
                if (!occupied[v]) {
                    if (find(v) != root)
                        ++result;
                } else if (capture(v))
                    ++result;
            });
            assert(0 <= result && result < N);
            answer[i - 1] = result;
        }
        return answer;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        Board board;
        board.read();
        auto answer = board.solve();
        for (int x : answer)
            cout << x << '\n';
    }
}