Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- minmov :
- - Giả sử ta đã sort các điểm lại theo pair
- - Truy vấn (S, T) : với S, T là 2 vị trí trên dãy sau khi sort và S < T
- - Nhận thấy các bước di chuyển từ S -> T chắc chắn phải có dạng LRLR hoặc RLRL
- +, giả sử đi 2 bước LL liên tục thì ta nhận thấy răng 2 bước đó là không cần thiết chỉ cần đi một bước L để đến mà thôi
- - Xây trước set<int> : Set[x] là tập các điểm có hoành độ là x
- - Xét bước L :
- +, Nhận thấy nếu tồn tại (x1, y1), (x2, y2) : x1 <= x2 && y1 <= y2 thì ta luôn nhảy đến (x1, y1)
- +, Vậy nếu ta đang ở vị trí (u, v) thì ta sẽ xây các tập điểm nhờ bước L thỏa mãn
- * i < j, Xi < Xj, Yi < Yj
- +, Ta có thể bỏ tập đó vào set để xử lí dễ dàng hơn.
- +, Với mỗi truy vấn (u, v) thì ta sẽ for lại trong tập của mình và xóa phần tử thỏa mãn (x, y) <= (u, v), và bổ sung
- thêm vào tập hợp hiện tại của mình thằng kế tiếp trong Set[x]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement