Codeforces Round #768 Div1C/Div2E Paint the Middle 题解

有段时间没做难一点的思维题了

思路 #

首先不难发现对于每个数来说，它的第一次和最后一次出现的位置是最重要的，因为使用其他位置的操作都可以使用两端的位置完成而且中间的位置的 c 值可以被两端变成 1。我们将每个数 $i$ 的第一次和最后一次位置记作 $l_i, r_i$ ，于是我们就可以将每个数表示成一个线段 $[l_i, r_i]$ 。

对于一个线段的集合 $S$ ，如果这些线段的并集等于线段 $[\min(l_i), \max(r_i)]$ ，我们称 $S$ 是连通的。对于所有线段我们可以将其划分为极大连通子集对于每个子集其互不影响所以最终的答案就是每个子集的答案之和。

对于每个极大子集 $S$ ，我们可能找到其最小子集 $S'\subseteq S$ 使得 $S'$ 中的线段的并等于 $S$ 中线段的并，这样我们可以将尽量多的线段的端点的 c 值变成 1.对于 $S'$ 中的线段我们可以证明最多可以将 $|S'|-1$ 个位置的 c 值变成 1。

代码 #

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> l(n, n), r(n, -1);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        x--;
        l[x] = min(l[x], i);
        r[x] = max(r[x], i);
    }
    vector<pair<int, int>> b, c;
    for (int i = 0; i < n; i++) {
        if (l[i] < r[i]) b.emplace_back(l[i], r[i]);
    }
    sort(begin(b), end(b));
    for (auto [l, r] : b) {
        // 去除在包含在其他线段之内的线段
        if (c.empty() || r > c.back().second) c.emplace_back(l, r);
    }
    int ans = 0, last = -1;
    int m = size(c);
    for (int i = 0; i < m; i++) {
        if (c[i].first > last) { // 新的子集的第一个线段，端点的 c 值无法变成 1
            ans += c[i].second - c[i].first - 1;
            last = c[i].second;
        } else if (i == m - 1 || c[i + 1].first > last) { // 子集中的其他线段，左端点 c 值会变成 1，会在之前被记入答案
            ans += c[i].second - last - 1;
            last = c[i].second;
        }
    }
    cout << ans << endl;
}