Editorial for Quân xe


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Đầu tiên, ta lưu ý rằng điều kiện để mỗi ô trong bàn cờ vua mới đều có thể bị tấn công bởi ít nhất một quân xe bất kỳ đó chính là mỗi hàng trong bàn cờ mới có ít nhất một quân xe, hoặc mỗi cột trong bàn cờ mới có ít nhất một quân xe.

Nhận thấy rằng ta có thể kiểm tra các điều kiện mỗi hàng và mỗi cột này một cách độc lập, đầu tiên ta sẽ xét cách để kiểm tra xem mỗi hàng trong bàn cờ mới có ít nhất một quân xe hay không. Ta thực hiện sắp xếp các query tăng dần theo ~y_2~ và các quân xe tăng dần theo ~y~. Tiếp đó, ta thực hiện sweepline/quét (các bạn có thể tham khảo thuật toán đường quét tại link này) qua các query, các quân xe từ trái sang phải (theo thứ tự tăng dần) theo ~y~. Giả sử bạn đang xét một query ~(x_1, y_1, x_2, y_2)~, gọi ~last(x)~ là giá trị ~y~ (thoả ~y \le y_2~) lớn nhất trong các quân xe thuộc hàng ~x~. Điều kiện để bàn cờ mới của query này có mỗi hàng đều có ít nhất một quân xe chính là ~y_1 \le last(i) \forall i \in [x_1, x_2]~ (tương đương ~y_1 \le \displaystyle\min^{x_2}_{i=x_1} (last(i))~). Việc tính ~\displaystyle\min^{x_2}_{i=x_1} (last(i))~ có thể được tính trong ~O(logn)~ dùng CTDL segment tree, và vì vậy với mỗi query ta chỉ tốn tối đa ~O(logn)~ thời gian để trả lời. Với bên kiểm tra mỗi cột cũng tương tự như vậy.

Độ phức tạp: ~O((k+q)log(n+m))~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.