思路:
注意看，只有一次改变颜色，不要再苦苦打二分了！
贪心地去求答案，对于每一种颜色记录两个点之间的距离的最大值和次大值，然后把最大值的那段区间的中点颜色更改成当前颜色。令最大值为 maxx，次大值为 max2。则 min(⌊maxx/2⌋,max2) 即为最优解。
记得处理到 n+1 号点的距离，该算法的时间复杂度为 O(n)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
const int INF=0x3f3f3f3f;
inline int read(){ll x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;}
ll t, m, n, a[N], maxx[N], pre[N], max2[N], ans;
int main() {
cin>>t;
for(int j=1;j<=t;++j) {
ans=INF;
cin>>n>>m;
for(int i=1;i<=m;++i) pre[i]=maxx[i]=max2[i]=0;
for(int i=1;i<=n;++i){
cin>>a[i];
if(i-pre[a[i]]-1>maxx[a[i]]){
max2[a[i]]=maxx[a[i]];
maxx[a[i]]=i-pre[a[i]]-1;
}
else
if(i-pre[a[i]]-1>max2[a[i]])
max2[a[i]]=i-pre[a[i]] - 1;
pre[a[i]]=i;
}
for(int i=1;i<=m;++i){
if(n-pre[i]>maxx[i]){
max2[i]=maxx[i];
maxx[i]=n-pre[i];
}
else
if(n-pre[i]>max2[i])max2[i]=n-pre[i];
ans=min(max(maxx[i] / 2, max2[i]), ans);
}
cout<<ans<<endl;
}
}