Mỗi vùng liên thông chọn \(1\) ô làm đại diện và đặt giá trị ô đó trên lưới bằng \(1\), các ô còn lại đặt bằng \(0\).

Với mỗi truy vấn:

• Tính tổng các ô \(1\) nằm trong hình chữ nhật (hình chữ nhật) của truy vấn đó (*)

• Các vùng liên thông thuộc hình chữ nhật nhưng chưa thuộc (*) thì ô đại diện nằm bên ngoài hình chữ nhật, ta có thể đếm các vùng này bằng cách xét các ô ở biên của hình chữ nhật vì vùng liên thông đó phải cắt qua cạnh hình chữ nhật.

Độ phức tạp: \(O(Q \times (m + n))\)