Codeforces Round #584 – Dasha Code Championship – Elimination Round (rated, open for everyone, Div. 1 + Div. 2) G1. Into Blocks (easy version)

题目：https://codeforc.es/contest/1209/problem/G1

题意：给你一个序列，要你进行一些操作后把他变成一个好序列，好序列的定义是，两个相同的数中间的数都要与他相同，可以把某一种数统一变成另一个数，问最少变得个数

思路：我们可以考虑贪心，对于一个互相牵扯的区间，我肯定是用总长减掉里面出现次数最多的元素才是最划得来的，我们直接求出这些牵扯区间的长度即可，方法就是我用数组记录每个元素出现最右的位置，然后从左到右遍历，我保留当前区间往右延伸的最长位置，然后减去出现最多即可，累加所有这种联通块

#include<bits/stdc++.h>#define maxn 200005#define mod 1000000007usingnamespace std;typedeflonglong ll;ll n,q,a[maxn];ll num[maxn],dex[maxn];int main(){ cin>>n>>q;for(int i=;i<=n;i++){ cin>>a[i]; num[a[i]]++; dex[a[i]]=i;} ll l=; ll ans=,mx=,r=;for(int i=;i<=n;i++){ r=max(r,dex[a[i]]); mx=max(mx,num[a[i]]);if(i==r){ ans+=r–l+-mx; mx=;l=r+; r=;}} cout<<ans;}