748.cpp

// 748 - Dynamic Quad Tree
//
// 實際建立 Quad Tree 並動態維護：
//   - build: 根據影像建樹，遇到均勻區域建葉節點，否則遞迴分四象限
//   - flip:  沿著根到像素的路徑走（深度 ≤ k ≤ 10）
//            遇到葉節點就拆分（split），翻轉後回溯嘗試收合（collapse）
//
// 每次翻轉只影響路徑上的 O(k) 個節點，非常高效
//
// 四象限定義（對於區域 [nr, nr+sz) × [nc, nc+sz)，令 h = sz/2）：
//   ch[0] = NW: [nr, nr+h) × [nc, nc+h)
//   ch[1] = NE: [nr, nr+h) × [nc+h, nc+sz)
//   ch[2] = SW: [nr+h, nr+sz) × [nc, nc+h)
//   ch[3] = SE: [nr+h, nr+sz) × [nc+h, nc+sz)

#include <iostream>
using namespace std;

const int MAXN = 1025;
const int MAXPOOL = 1500000;

struct Node {
    int ch[4];
    int cnt;
    int color;
    bool isLeaf;
};

Node pool[MAXPOOL];
int poolCnt;
char grid[MAXN][MAXN];

int newLeaf(int color) {
    int id = poolCnt++;
    pool[id].ch[0] = pool[id].ch[1] = pool[id].ch[2] = pool[id].ch[3] = -1;
    pool[id].cnt = 1;
    pool[id].color = color;
    pool[id].isLeaf = true;
    return id;
}

// 建樹：由上而下，先檢查區域是否均勻
// 均勻 → 葉節點（1 node）；否則 → 內部節點 + 遞迴 4 子區域
int build(int r, int c, int sz) {
    if (sz == 1) return newLeaf(grid[r][c] - '0');

    char first = grid[r][c];
    bool uniform = true;
    for (int i = r; i < r + sz && uniform; i++)
        for (int j = c; j < c + sz && uniform; j++)
            if (grid[i][j] != first) uniform = false;

    if (uniform) return newLeaf(first - '0');

    int id = poolCnt++;
    pool[id].isLeaf = false;
    int h = sz / 2;
    pool[id].ch[0] = build(r, c, h);
    pool[id].ch[1] = build(r, c + h, h);
    pool[id].ch[2] = build(r + h, c, h);
    pool[id].ch[3] = build(r + h, c + h, h);
    pool[id].cnt = 1;
    for (int q = 0; q < 4; q++)
        pool[id].cnt += pool[pool[id].ch[q]].cnt;
    return id;
}

// 翻轉像素 (pr, pc)，從節點 id（代表區域 [nr,nr+sz)×[nc,nc+sz)）開始
void flip(int id, int nr, int nc, int sz, int pr, int pc) {
    if (sz == 1) {
        pool[id].color ^= 1;
        return;
    }

    // 葉節點被翻轉 → 必須拆分成 4 個同色子節點
    if (pool[id].isLeaf) {
        pool[id].isLeaf = false;
        int c = pool[id].color;
        for (int q = 0; q < 4; q++)
            pool[id].ch[q] = newLeaf(c);
    }

    // 判斷像素落在哪個象限
    int h = sz / 2;
    int ri = (pr >= nr + h) ? 1 : 0;
    int ci = (pc >= nc + h) ? 1 : 0;
    int q = ri * 2 + ci;

    flip(pool[id].ch[q], nr + ri * h, nc + ci * h, h, pr, pc);

    // 回溯：嘗試收合（4 個子節點都是同色葉 → 合併為 1 個葉）
    bool canCollapse = true;
    int fc = pool[pool[id].ch[0]].color;
    for (int i = 0; i < 4; i++) {
        if (!pool[pool[id].ch[i]].isLeaf || pool[pool[id].ch[i]].color != fc) {
            canCollapse = false;
            break;
        }
    }

    if (canCollapse) {
        pool[id].isLeaf = true;
        pool[id].color = fc;
        pool[id].cnt = 1;
    } else {
        pool[id].cnt = 1;
        for (int i = 0; i < 4; i++)
            pool[id].cnt += pool[pool[id].ch[i]].cnt;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        poolCnt = 0;

        int k;
        cin >> k;
        int n = 1 << k;

        for (int i = 0; i < n; i++) cin >> grid[i];

        int root = build(0, 0, n);

        int m;
        cin >> m;
        while (m--) {
            int r, c;
            cin >> r >> c;
            r--; c--;
            flip(root, 0, 0, n, r, c);
            cout << pool[root].cnt << "\n";
        }
    }

    return 0;
}