Khối Phô Mai Của FJ

Lời giải: Khối Phô Mai Của FJ

Hướng tiếp cận

Theo dõi số khối phô mai còn lại trên mỗi đường thẳng song song với các trục tọa độ.

Nhận xét quan trọng

Viên gạch $1\times 1\times N$ chỉ có 3 hướng đặt: song song với trục $x$, $y$, hoặc $z$. Với mỗi hướng, viên gạch chiếm trọn một hàng $N$ ô liên tiếp. Viên gạch đặt được khi và chỉ khi toàn bộ $N$ ô trên hàng đó đã bị cắt hết.

Thuật toán

Duy trì 3 mảng 2D kích thước $N\times N$:

• xy[x][y]: số ô phô mai còn lại trên đường song song trục $z$ qua $(x,y)$
• xz[x][z]: số ô còn lại trên đường song song trục $y$ qua $(x,z)$
• yz[y][z]: số ô còn lại trên đường song song trục $x$ qua $(y,z)$

Khi cắt ô $(x,y,z)$: giảm 3 bộ đếm tương ứng. Mỗi khi bộ đếm về $0$, tăng đáp án thêm $1$.

Độ phức tạp

• Thời gian: $O(N^2+Q)$
• Bộ nhớ: $O(N^2)$