Into Blocks (easy version)

Created by LXC on Mon Aug 21 20:51:24 2023

https://codeforces.com/problemset/problem/1209/G1

ranting: 2000

tag: data structures, dsu, greedy, implementation, two pointers

problem

给出n个数，每个数的范围在1到n内。

现在定义nice数组为任意两个相当的数之间的所有数都得等于这两个数。

每次操作可以让任意一个数变为另一数，但是有一个限制就是对于一个x变为了y，其他x也应改为y。

现在求当前数组变为nice数组的最少操作次数。

n <= 200000

solution

注意到，对于一个数x，我们只需要考虑最开始出现的位置l和最后出现的位置r。区间[l,r]内的数应当全部相等。

但是可能会有多个这样的区间相交，所以我们要将这些区间合并，合并后的大区间内的数应相等。这时候我们统计这个区间内出现得最多的数，这些数不用改变，这样才能操作次数最少。

数组中的每个数的值最大不超过数组长度。所以我们可以得到最多不超过n个区间，然后将这些区间中相交的合并，再统计每个区间对答案的贡献。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 200005
#define MOD 998244353
using namespace std;

int a[N], l[N], r[N], h[N];

void sol() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        r[a[i]] = i;
    }
    for (int i = n; i >= 1; i--) {
        l[a[i]] = i;
    }
    vector<int> sp(1, 0);
    for (int i = 1; i <= n; i++) {
        if (i > sp.back())
            sp.push_back(r[a[i]]);
        sp.back() = max(sp.back(), r[a[i]]);
    }
    // for (int i : sp)
    //     cout << i << " ";
    // cout << endl;
    int ans = 0;
    for (int i = 1; i < sp.size(); i++) {
        int mx = 0;
        for (int j = sp[i - 1] + 1; j <= sp[i]; j++) {
            mx = max(mx, ++h[a[j]]);
        }
        ans += sp[i] - sp[i - 1] - mx;
        for (int j = sp[i - 1] + 1; j <= sp[i]; j++) {
            h[a[j]] = 0;
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}