概要

\(H \times W\) の照明パネルに対して \(N\) 回の矩形反転操作を行った後の最終状態を求め、\(M\) 個のクエリそれぞれについて、指定矩形内の点灯マス数と、完全に矩形内に収まる島（連結成分）の数を答える問題です。

考察

最終状態の構築

各マスは偶数回反転されれば消灯、奇数回反転されれば点灯します。つまり反転回数の偶奇だけが重要です。これは通常の加算による2次元累積和ではなく、2次元 XOR いもす法で効率的に求められます。

通常のいもす法では diff[a][c] += 1, diff[a][d+1] -= 1, ... とするところを、XOR では diff[a][c] ^= 1, diff[a][d+1] ^= 1, ... とします。XOR は自身の逆演算（\(x \oplus x = 0\)）なので、加減算の代わりに全て XOR で統一できます。

点灯マス数のクエリ

矩形内の点灯マス数は、最終状態のグリッドに対する2次元累積和を前計算しておけば \(O(1)\) で答えられます。

島の完全包含判定

島が矩形 \([P, Q] \times [R, S]\) に完全に収まっているかを判定するには、各島のバウンディングボックス（最小外接矩形）を使います。島のバウンディングボックス \([\text{minr}, \text{maxr}] \times [\text{minc}, \text{maxc}]\) がクエリ矩形に含まれていれば、その島の全マスも含まれています。

クエリごとに矩形内のマスを走査し、未チェックの島に出会ったらバウンディングボックスで包含判定を行います。制約 \(M \times H \times W \leq 5 \times 10^7\) により、この全走査が間に合います。

アルゴリズム

1. 2次元 XOR いもす法で最終状態のグリッドを \(O(H \times W + N)\) で構築
2. 2次元累積和を前計算し、点灯マス数クエリに \(O(1)\) で対応
3. BFS で全島を探索し、各島に ID を振り、バウンディングボックスを記録（\(O(H \times W)\)）
4. 各クエリについて、矩形内を走査：
   • 点灯マスの島 ID を確認し、まだこのクエリで訪問していなければ、バウンディングボックスがクエリ矩形に包含されるか \(O(1)\) で判定
   • 訪問済み管理には visited[id] = クエリ番号 というテクニックを使い、毎回配列を初期化する手間を省く

計算量

• 時間計算量: \(O(H \times W + N + \sum_{j=1}^{M}(Q_j - P_j + 1)(S_j - R_j + 1))\)
  • 制約 \(M \times H \times W \leq 5 \times 10^7\) によりクエリ走査部分は全体で最大 \(5 \times 10^7\) 程度
• 空間計算量: \(O(H \times W + K)\)（\(K\) は島の数）

実装のポイント

• 2次元 XOR いもす法の復元: 通常の累積和の復元と同様に左上から順に処理しますが、演算が全て XOR になります：

  diff[r][c] ^= diff[r-1][c] ^ diff[r][c-1] ^ diff[r-1][c-1]
  

  加算の場合の +, +, - が XOR では ^, ^, ^ になるのは、XOR が自身の逆演算であるためです。

• visited 配列の再利用: visited[idx] != q（q はクエリ番号）でそのクエリで未訪問かを判定します。これにより各クエリごとに配列を \(O(K)\) で初期化する必要がなくなります。

• バウンディングボックスによる包含判定: 島の全マスを調べる代わりに、\(\text{minr} \geq P\) かつ \(\text{maxr} \leq Q\) かつ \(\text{minc} \geq R\) かつ \(\text{maxc} \leq S\) の4条件で \(O(1)\) 判定できます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int H, W, N;
    cin >> H >> W >> N;
    
    // 2D XOR difference array
    vector<vector<int>> diff(H+2, vector<int>(W+2, 0));
    for(int i = 0; i < N; i++){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        diff[a][c] ^= 1;
        diff[a][d+1] ^= 1;
        diff[b+1][c] ^= 1;
        diff[b+1][d+1] ^= 1;
    }
    
    // Build grid
    vector<vector<int>> grid(H+1, vector<int>(W+1, 0));
    for(int r = 1; r <= H; r++){
        for(int c = 1; c <= W; c++){
            diff[r][c] ^= diff[r-1][c] ^ diff[r][c-1] ^ diff[r-1][c-1];
            grid[r][c] = diff[r][c];
        }
    }
    
    // 2D prefix sum for lit cells
    vector<vector<int>> psum(H+1, vector<int>(W+1, 0));
    for(int r = 1; r <= H; r++)
        for(int c = 1; c <= W; c++)
            psum[r][c] = grid[r][c] + psum[r-1][c] + psum[r][c-1] - psum[r-1][c-1];
    
    // BFS to find islands
    vector<vector<int>> id(H+1, vector<int>(W+1, 0));
    int num_islands = 0;
    // bounding box: minr, maxr, minc, maxc
    vector<array<int,4>> bbox;
    bbox.push_back({0,0,0,0}); // dummy for 0-index
    
    int dr[] = {-1,1,0,0};
    int dc[] = {0,0,-1,1};
    
    for(int r = 1; r <= H; r++){
        for(int c = 1; c <= W; c++){
            if(grid[r][c] && !id[r][c]){
                num_islands++;
                int minr=r, maxr=r, minc=c, maxc=c;
                queue<pair<int,int>> q;
                q.push({r,c});
                id[r][c] = num_islands;
                while(!q.empty()){
                    auto [cr, cc] = q.front(); q.pop();
                    for(int d = 0; d < 4; d++){
                        int nr = cr+dr[d], nc = cc+dc[d];
                        if(nr>=1 && nr<=H && nc>=1 && nc<=W && grid[nr][nc] && !id[nr][nc]){
                            id[nr][nc] = num_islands;
                            minr = min(minr, nr);
                            maxr = max(maxr, nr);
                            minc = min(minc, nc);
                            maxc = max(maxc, nc);
                            q.push({nr,nc});
                        }
                    }
                }
                bbox.push_back({minr, maxr, minc, maxc});
            }
        }
    }
    
    // Answer queries
    int M;
    cin >> M;
    
    vector<int> visited(num_islands+1, 0);
    
    for(int q = 1; q <= M; q++){
        int P,Q,R,S;
        cin >> P >> Q >> R >> S;
        
        int lit = psum[Q][S] - psum[P-1][S] - psum[Q][R-1] + psum[P-1][R-1];
        
        int island_count = 0;
        for(int r = P; r <= Q; r++){
            for(int c = R; c <= S; c++){
                if(grid[r][c]){
                    int idx = id[r][c];
                    if(visited[idx] != q){
                        visited[idx] = q;
                        auto& b = bbox[idx];
                        if(b[0] >= P && b[1] <= Q && b[2] >= R && b[3] <= S){
                            island_count++;
                        }
                    }
                }
            }
        }
        
        cout << lit << ' ' << island_count << '\n';
    }
    
    return 0;
}

この解説は claude4.6opus-thinking によって生成されました。