Ta nhận thấy rằng:

• Nếu một hình vuông mới thêm vào không có chung cạnh với hình vuông nào khác thì tổng chu vi tăng lên $4$.
• Nếu một hình vuông mới thêm vào có chung cạnh với $k$ hình vuông khác thì tổng chu vi tăng lên $4 - 2k$, vì cạnh chung này thay vì được cộng thì lại bị trừ vào chu vi thêm vào.

Do đó ta có thể lập một mảng $cnt[i][j]$ lưu trạng thái của ô có góc trái dưới là $(i, j)$ (có hay không có hình vuông), từ đó tính được ngay số hình vuông chung cạnh với hình vuông được thêm vào ở mỗi truy vấn.

Độ phức tạp: $O(q)$