Into Blocks（不带修改的 E a s y Easy Easy版本）

题意：给定一个序列，通过改变其中的数字使所有相同的数字在数组中都是相邻的，改变数字的方式为：将数组中某个数字全部修改为另外一个数字。求最少需要改变的元素
思路：

  1. 由于最终状态肯定是“一块一块”的，每一块中都是一样的数字
  2. 因此考虑预处理每种数字最靠右的位置，然后从左到右扫描整个序列
  3. 扫描的过程中以出现的数字的最靠右的位置为界限，并且每遇到一个新数字就更新界限
  4. 而当扫描到界限位置出，表明改变当前区域内的数字不会影响到后面的区域，因此找出当前区域内出现次数最多的数字，并且把其他数字都改为当前数字即为最优
  5. 妙啊！heyuhhh nb!

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
 
const int maxn = 2e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;
 
int n, q, ans;
int a[maxn], x[maxn], cnt[maxn];
inline void max(int &a, int b) { if(a<b) a=b; }
 
int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), q=read();
	for(int i=1; i<=n; ++i) cnt[x[a[i]=read()]=i,a[i]]++;
	for(int i=1; i<=n; ++i) {
		int l=i, r=x[a[i]], m=cnt[a[i]];
		while(i<r) ++i, max(r,x[a[i]]), max(m,cnt[a[i]]);
		ans+=r-l+1-m;
	}
	cout<<ans<<endl;
}

压行过猛，竟然压到第一了

#include"bits/stdc++.h"
const int N=2e5+1;
int i,n,q,p,l,r,m,a[N],x[N],c[N];
int main(){
    scanf("%d%d",&n,&q);
	for(i=1;i<=n;++i)scanf("%d",&a[i]),c[x[a[i]]=i,a[i]]++;
	for(i=1;i<=n;++i){
		l=i,r=x[a[i]],m=c[a[i]];
		while(i<r)++i,r=std::max(r,x[a[i]]),m=std::max(m,c[a[i]]);
		p+=r-l+1-m;
	}
	printf("%d",p);
}