Subtask 1

• ~N \le 1000~

Ở subtask này ta có thể thử chèn lần lượt các lệnh L, R, U, D ở từng vị trí sau đó duyệt lại chuỗi mới từ đầu.

Kết hợp với cấu trúc dữ liệu như std :: map hoặc std :: set sẽ cho ta độ phức tạp ~O(N^2logN)~.

Subtask 2

• ~N \le 2 \times 10^5~

Đầu tiên ta lưu lại thứ tự tọa độ thăm của robot khi thực hiện dãy lệnh ban đầu.

Gọi ~\text{move_x[c]}~ và ~\text{move_y[c]}~ lần lượt là lượng dịch của hoành độ và tung độ khi ta thực hiện lệnh ~c~.

Khi ta thêm một lệnh ~c~ vào sau vị trí ~i~ thì mọi vị trí ~\text{pos[j] = (x, y)}, i < j \le n~ mà robot đã đi qua sau lệnh thứ ~i~ sẽ thay đổi thành ~\text{pos[j] = (x + move_x[c], y + move_y[c])}~.

Nhận xét, khi ta đã thử thêm một lệnh ~c~ ở vị trí ~i~, sau đó ta lại thử lệnh ~c~ ở vị trí ~i + 1~ thì sự khác nhau giữa hai lần này chỉ có ở vị trí ~pos[i + 1]~, ở lần thêm sau thì vị trí này vẫn giữ nguyên.

Do đó nếu đang xét riêng việc thêm lệnh ~c~, thì ta có thể duyệt ngược từ cuối về để vừa có thể dịch phần hậu tố theo lệnh vừa thêm.

Độ phức tạp ~O(NlogN)~