题解 | 小O的数组染色

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

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<long long> a(n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        // 记录每个值的首末位置
        unordered_map<long long, pair<int, int>> pos;
        pos.reserve(n * 2);
        for (int i = 1; i <= n; ++i) {
            auto& pr = pos[a[i]];
            if (pr.first == 0) pr.first = i;   // 首次出现
            pr.second = i;                     // 不断更新为最后出现
        }
        // 收集区间 [first(v), last(v)]
        vector<pair<int, int>> segs;
        segs.reserve(pos.size());
        for (auto& kv : pos) segs.push_back(kv.second);
        // 按左端点排序
        sort(segs.begin(), segs.end());
        // 贪心覆盖 [1..n]
        int ans = 0, i = 0, R = 0;
        while (R < n) {
            int best = R;
            while (i < (int)segs.size() && segs[i].first <= R + 1) {
                best = max(best, segs[i].second);
                ++i;
            }
            // 一定能推进：因为位置 R+1 属于某个值 v，其区间必以 L<=R+1 覆盖它
            ++ans;
            R = best;
        }
        cout << ans << '\n';
    }
    return 0;
}