Tóm tắt đề bài

Cho dãy số \(A\) gồm \(N\) phần tử, các phần tử có giá trị từ \(1\) đến \(K\). Một dãy đầy đủ bậc \(K\) là một hoán vị của các số từ \(1\) đến \(K\). Hãy tìm dãy con của \(A\) sao cho dãy đó là một dãy đầy đủ bậc \(K\) và có thứ tự từ điển nhỏ nhất.

Phân tích

• Dãy đầy đủ bậc \(K\): Là dãy chứa mỗi số từ \(1\) đến \(K\) đúng một lần.
• Thứ tự từ điển nhỏ nhất: Ta ưu tiên chọn số nhỏ nhất có thể cho vị trí đầu tiên, sau đó đến vị trí thứ hai, và cứ tiếp tục như vậy.
• Ràng buộc quan trọng: Khi chọn một số ở vị trí \(i\) trong dãy gốc \(A\) để làm phần tử tiếp theo của dãy kết quả, ta phải đảm bảo rằng các số còn lại (chưa được chọn) vẫn xuất hiện ở các vị trí sau \(i\) trong dãy \(A\). Nếu không, ta sẽ không thể hoàn thành một dãy đầy đủ bậc \(K\).

Hướng giải quyết

Nhận xét chiến thuật tham lam

Giả sử ta đang cần chọn phần tử tiếp theo cho dãy kết quả, và vị trí cuối cùng đã chọn trong dãy \(A\) là pre. Ta cần tìm một giá trị \(v\) nhỏ nhất xuất hiện tại vị trí \(pos\) (\(pos > pre\)) sao cho:

• Giá trị \(v\) chưa được chọn trước đó.
• Sau vị trí \(pos\), tất cả các giá trị còn lại (chưa được chọn) đều phải xuất hiện ít nhất một lần nữa.

Để thực hiện điều này một cách hiệu quả, ta cần quản lý:

1. Vị trí xuất hiện cuối cùng của mỗi giá trị từ \(1\) đến \(K\) trong dãy \(A\). Gọi \(last[v]\) là vị trí cuối cùng của giá trị \(v\).
2. Trong số các giá trị chưa được chọn, giá trị nào có vị trí xuất hiện cuối cùng sớm nhất? Gọi vị trí đó là \(cur = \min(last[v])\) với mọi \(v\) chưa chọn.
3. Mọi số ta chọn ở bước hiện tại phải nằm trong đoạn \([pre, cur]\). Nếu ta chọn một số ở vị trí sau \(cur\), ta sẽ "bỏ lỡ" mất giá trị có \(last[v] = cur\) và không bao giờ hoàn thành được dãy đầy đủ bậc \(K\).

Thuật toán chi tiết

1. Khởi tạo mảng \(last[v]\) lưu vị trí cuối cùng của mỗi số \(v \in [1, K]\).
2. Sử dụng hai cấu trúc dữ liệu Segment Tree:
   • IT1: Quản lý các giá trị \(A[i]\) và vị trí \(i\) của chúng để tìm giá trị nhỏ nhất trong một khoảng \([pre, cur]\).
   • IT2: Quản lý các giá trị \(last[v]\) của các số \(v\) chưa được chọn để tìm \(cur = \min(last[v])\).
3. Lặp \(K\) lần để tìm \(K\) phần tử:
   • Xác định giới hạn phải \(cur = \text{IT2.query_min()}\).
   • Tìm giá trị nhỏ nhất \(v\) và vị trí \(pos\) của nó trong đoạn \([pre, cur]\) bằng IT1.
   • In giá trị \(v\) ra kết quả.
   • Cập nhật IT1: Xóa tất cả các vị trí xuất hiện của giá trị \(v\) vừa chọn (đặt bằng \(\infty\)) để không chọn lại.
   • Cập nhật IT2: Xóa giá trị \(last[v]\) (đặt bằng \(\infty\)).
   • Cập nhật vị trí bắt đầu cho lần chọn kế tiếp: \(pre = pos + 1\).

Độ phức tạp

• Thời gian: \(O(N \log N + K \log K)\). Với mỗi phần tử trong dãy \(A\), ta có thể thực hiện update trên Segment Tree. Có \(K\) bước chọn, mỗi bước thực hiện query trên Segment Tree.
• Bộ nhớ: \(O(N + K)\) để lưu trữ dãy số và Segment Tree.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

#define T pair<int,int>
const int maxn = 1e5 + 4;
const int INF = 1e9;

int n, k, last[maxn], a[maxn];
vector<int> myVec[maxn]; // Lưu tất cả các vị trí xuất hiện của từng giá trị

struct segTree {
    vector<T> t;
    segTree() { t.resize(4 * maxn); }

    // f=0: build cho IT1 (giá trị a[i], vị trí i)
    // f=1: build cho IT2 (vị trí cuối cùng last[i], giá trị i)
    void build(int v, int l, int r, bool f) {
        if (l == r) {
            t[v] = (f ? T(last[l], l) : T(a[l], l));
            return;
        }
        int m = (l + r) / 2;
        build(2 * v, l, m, f);
        build(2 * v + 1, m + 1, r, f);
        t[v] = min(t[2 * v], t[2 * v + 1]);
    }

    void update(int pos, int v, int l, int r) {
        if (l == r) {
            t[v] = T(INF, INF);
            return;
        }
        int m = (l + r) / 2;
        if (pos <= m) update(pos, 2 * v, l, m);
        else update(pos, 2 * v + 1, m + 1, r);
        t[v] = min(t[2 * v], t[2 * v + 1]);
    }

    T get(int l, int r, int v, int tl, int tr) {
        if (tl > r || tr < l) return T(INF, INF);
        if (tl >= l && tr <= r) return t[v];
        int m = (tl + tr) / 2;
        return min(get(l, r, 2 * v, tl, m), get(l, r, 2 * v + 1, m + 1, tr));
    }
} IT, IT2;

void Solve() {
    if (!(cin >> n >> k)) return;
    for (int i = 1; i <= k; i++) myVec[i].clear();
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        last[a[i]] = i;
        myVec[a[i]].push_back(i);
    }

    IT.build(1, 1, n, 0);   // Quản lý giá trị các phần tử trong dãy A
    IT2.build(1, 1, k, 1);  // Quản lý vị trí cuối cùng của các số từ 1..K

    int pre = 1;
    for (int i = 1; i <= k; i++) {
        // Giới hạn phải: vị trí cuối cùng nhỏ nhất của các số chưa chọn
        int cur = IT2.t[1].first; 

        // Tìm giá trị nhỏ nhất trong đoạn khả thi [pre, cur]
        T it = IT.get(pre, cur, 1, 1, n);
        int val = it.first;
        int pos = it.second;

        cout << val << (i == k ? "" : " ");

        // Xóa tất cả các vị trí của giá trị 'val' đã chọn trong IT1
        for (int p : myVec[val])
            IT.update(p, 1, 1, n);

        // Xóa giá trị 'val' khỏi IT2
        IT2.update(val, 1, 1, k);

        // Cập nhật vị trí bắt đầu mới
        pre = pos + 1;
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) {
        Solve();
    }
    return 0;
}