Following Directions

Lời giải: Following Directions

Hướng tiếp cận

Duy trì mảng 2D $A[i][j]$ đếm số bò đi qua mỗi ô. Khi đổi biển chỉ hướng, chỉ cần cập nhật các ô trên đường đi cũ và mới.

Thuật toán

1. Khởi tạo ($O(N^2)$): Tính $A[i][j]$ cho tất cả các ô bằng cách lan truyền theo hướng biển.
2. Truy vấn ($O(N)$): Khi đổi biển ở $(i,j)$:
   • Trừ $A[i][j]$ trên đường đi cũ (từ ô kế tiếp đến máng).
   • Đổi hướng biển.
   • Cộng $A[i][j]$ trên đường đi mới.
   • Cập nhật tổng chi phí.

Độ phức tạp

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