Overview

Given an \(H \times W\) lighting panel on which \(N\) rectangular flip operations are performed, determine the final state, and for each of \(M\) queries, answer the number of lit cells within the specified rectangle and the number of islands (connected components) that are completely contained within the rectangle.

Analysis

Constructing the Final State

Each cell is off if flipped an even number of times, and on if flipped an odd number of times. In other words, only the parity of the flip count matters. This can be efficiently computed not with the usual addition-based 2D prefix sums, but with a 2D XOR imos method.

In the standard imos method, we do diff[a][c] += 1, diff[a][d+1] -= 1, ..., but with XOR, we do diff[a][c] ^= 1, diff[a][d+1] ^= 1, .... Since XOR is its own inverse operation (\(x \oplus x = 0\)), we can unify everything with XOR instead of addition and subtraction.

Lit Cell Count Queries

The number of lit cells within a rectangle can be answered in \(O(1)\) by precomputing a 2D prefix sum on the final state grid.

Complete Containment of Islands

To determine whether an island is completely contained within a rectangle \([P, Q] \times [R, S]\), we use each island’s bounding box (minimum enclosing rectangle). If the island’s bounding box \([\text{minr}, \text{maxr}] \times [\text{minc}, \text{maxc}]\) is contained within the query rectangle, then all cells of that island are also contained.

For each query, we scan through the cells within the rectangle, and when we encounter an unchecked island, we perform the containment check using the bounding box. Due to the constraint \(M \times H \times W \leq 5 \times 10^7\), this full scan is fast enough.

Algorithm

1. Construct the final state grid in \(O(H \times W + N)\) using the 2D XOR imos method
2. Precompute 2D prefix sums to answer lit cell count queries in \(O(1)\)
3. Explore all islands using BFS, assign each island an ID, and record their bounding boxes (\(O(H \times W)\))
4. For each query, scan through the rectangle:
   • Check the island ID of each lit cell; if it hasn’t been visited for this query yet, determine in \(O(1)\) whether the bounding box is contained within the query rectangle
   • For visited management, use the technique visited[id] = query number to avoid the overhead of reinitializing the array each time

Complexity

• Time complexity: \(O(H \times W + N + \sum_{j=1}^{M}(Q_j - P_j + 1)(S_j - R_j + 1))\)
  • Due to the constraint \(M \times H \times W \leq 5 \times 10^7\), the query scanning portion is at most around \(5 \times 10^7\) in total
• Space complexity: \(O(H \times W + K)\) (where \(K\) is the number of islands)

Implementation Details

• Restoring the 2D XOR imos method: Similar to restoring a standard prefix sum, we process from the top-left corner, but all operations are XOR:

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

  The +, +, - in the addition case becomes ^, ^, ^ in XOR because XOR is its own inverse operation.

• Reusing the visited array: We check visited[idx] != q (where q is the query number) to determine if the island is unvisited for that query. This eliminates the need to initialize the array in \(O(K)\) for each query.

• Containment check using bounding boxes: Instead of examining all cells of an island, we can perform an \(O(1)\) check with four conditions: \(\text{minr} \geq P\) and \(\text{maxr} \leq Q\) and \(\text{minc} \geq R\) and \(\text{maxc} \leq S\).

  Source Code

#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;
}

This editorial was generated by claude4.6opus-thinking.