Để ac bài này cũng không khó và có thể giải quyết trong
Ta nhận thấy rằng với mỗi truy vấn 1 ta chỉ mất để tô (tô phòng có chỉ số tăng dần)
Nhưng để hỗ trợ cho truy vấn 2 ta phải thêm một giá trị lưu được nhóm màu, gọi một vector là danh sách những phòng có màu i
VD:
đỏ 1 2 3 4 5
xanh 6 7 8 9
Như vậy khi thực hiện đổi tất cả phòng màu đỏ thành màu xanh ta chỉ việc chuyển hết giá trị sang , thế nhưng độ phức tạp khi chuyển là O(n) nên sẽ không AC. Vì thế ta không được dùng vector để lưu mà phải dùng một kiểu dữ liệu gì đó tương tự nhưng chi phí chuyển đổi thấp
Câu trả lời là dùng trace với chi phí là O(1)
Nhưng vậy với mỗi truy vấn một ta chỉ việc lưu tiếp vào trace của màu đó.
Nhưng vậy mảng trace của chúng ta cần lưu giá trị là chỉ số trace tiếp theo Và giờ ta chỉ việc dùng mp[i] là để lưu chỉ số trace đầu và trace cuối
VD:
trace [0] = 1;
trace [1] = 2;
trace [2] = 3;
trace [3] = 4;
trace [4] = -1;
mp[đỏ] = {0, 4};
trace [5] = 6;
trace [6] = -1
mp[xanh] = {5, 6};
Khi ghép thằng đỏ vào xanh
=> mp[đỏ] = {-1, -1};
trace[mp[xanh] -> End] = trace[mp[đỏ] -> Begin];
mp[xanh] = mp[đỏ] -> End;
Như vậy ta đã xử lý xong phần truy vấn, còn lại phần kết quả bạn có thể for từ 'a' -> 'z' và lưu giá trị đó vào một string
Chúc các bạn thành công :D
Tổng cộng 1 trả lời
Có một cách đơn giản hơn như sau:
VD : 1 u ta thêm mp['u'] vào cuối sâu S