Bài này là một bài không quá khó, đơn giản ta có một thuật toán đề bài bảo gì ta làm nấy là cũng giải quết được sub1() với thuật toán O(n^2)

Để 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