分析

考虑这么个过程。当我们定下了最终两个颜色，就挨个位置地推整个颜色序列。假设最终定下的奇数位为 $a$，偶数位为 $b$，那么当且仅当遇到连续的一段偶数位为 $a$，奇数位为 $b$ 的时候才会需要额外操作。注意到一段长度为 $k$ 的这么个交替连续段，需要的操作是除以二下取整，理由是先把较少的那一个数全部变为 $0$，再把剩下的数复原，然后把变为 $0$ 的数变回去应该是的值，现在目标变成了统计有多少位置会需要额外操作。我们考虑只有相邻两个数作为奇数或偶数位的时候才会出现额外操作，这样的数只有至多 $n-1$ 对，可以进行枚举。对于不会出现额外操作的数对，考虑先将会出现额外操作的数对记录下来，当枚举奇数位填什么的时候直接去除之前记录过的额外操作数对，这样直接在剩下中找到最值即可。这个可以使用 multiset 维护。

注意一定不要用 set 存 pair，这个的运行时间是 multiset 存 int 的 $17$ 倍左右！！

AC Code

#include <bits/stdc++.h>
using namespace std;
int o[200010],e[200010],a[200010],vis[200010];
basic_string<int> del[200010],del2[200010];
unordered_map<int,int> mp[200010];
multiset<int> sto,ste;
inline auto c(int i)
{
	if(i&1) return make_pair(a[i],a[i+1]);
	return make_pair(a[i+1],a[i]);
}
void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		o[i]=e[i]=vis[i]=0,del[i].clear(),del2[i].clear();
		del[i].shrink_to_fit();del2[i].shrink_to_fit();
		unordered_map<int,int> ().swap(mp[i]);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(i&1)	o[a[i]]++;
		else e[a[i]]++;
	}
	sto.clear();ste.clear();
	for(int i=1;i<=n;i++) sto.insert(-o[i]),ste.insert(-e[i]);
	int k=0;
	pair<int,int> lst={0,0};
	for(int i=1;i<n;i++)
	{
		if(c(i)!=lst) mp[lst.first][lst.second]+=(k+1)>>1,k=1,lst=c(i);
		else k++;
	}
	mp[lst.first][lst.second]+=(k+1)>>1;
	int ans1=1e9;
	for(int i=1;i<=n;i++)
	{
		for(auto [j,x]:mp[i])
		{
			ans1=min(ans1,-e[i]-o[j]+x);
			del[i].push_back(j);
			del2[j].push_back(i);
		}
	}
	for(int i=1;i<=n;i++) if(!del[i].empty()) del[i].push_back(i),sort(del[i].begin(),del[i].end(),[](int x,int y){return (o[x]!=o[y]?o[x]>o[y]:x<y);}),del[i].erase(unique(del[i].begin(),del[i].end()),del[i].end());
	for(int i=1;i<=n;i++) if(!del2[i].empty()) del2[i].push_back(i),sort(del2[i].begin(),del2[i].end(),[](int x,int y){return (e[x]!=e[y]?e[x]>e[y]:x<y);}),del2[i].erase(unique(del2[i].begin(),del2[i].end()),del2[i].end());
	int ans2=1e9;
	for(int i=1;i<=n;i++)
	{
		if(i&1)
		{
			int tot=-1;
			for(int j=0;j<del2[a[i]].size();j++)
			{
				if(ste.empty()||-e[del2[a[i]][j]]!=*ste.begin())
				{
					tot=j;
					break;
				}
				ste.erase(ste.begin());
			}
			if(!~tot) tot=del2[a[i]].size();
			if(!ste.empty()) ans2=min(ans2,-o[a[i]]+*ste.begin());
			for(int j=0;j<tot;j++) ste.insert(-e[del2[a[i]][j]]);
		}
		else
		{
			int tot=-1;
			for(int j=0;j<del[a[i]].size();j++)
			{
				if(sto.empty()||-o[del[a[i]][j]]!=*sto.begin())
				{
					tot=j;
					break;
				}
				sto.erase(sto.begin());
			}
			if(!~tot) tot=del[a[i]].size();
			if(!sto.empty()) ans2=min(ans2,-e[a[i]]+*sto.begin());
			for(int j=0;j<tot;j++) sto.insert(-o[del[a[i]][j]]);
		}
	}
	cout<<min(ans1,ans2)+n<<'\n';
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--) solve();
}