专栏文章

题解：CF2085F2 Serval and Colorful Array (Hard Version)

eelswzl
CF2085F2题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mippuslv
此快照首次捕获于
2025/12/03 15:59
3 个月前
此快照最后确认于
2025/12/03 15:59
3 个月前
查看原文

思路

首先想到一个小结论：假如我们已经钦定好了最后要组成排列的所有数字，定义第 ii 所在的位置为 pip_i，那么如何让它们贴在一起的代价最小？显然是向 pp 的中位数处靠拢，这下真读者自证不难了。
然后又发现了一个小结论：如果我们已经确定了 pp 都要向 ii 处靠拢，那么应该如何确定数组 pp 呢？每种数字肯定都是越靠近 ii 越好的,也就是 ii 前后最接近 ii 的数字是有用的，故我们定义数组 AjA_j 和 BjB_j 分别表示对于数字 jj，在 ii 和之前下标最大 jj 和 ii 之后下标最小的 jj 是什么。
设 l=⌊m2⌋,r=m−ll=\lfloor\frac{m}{2}\rfloor,r=m-l 表示 ii 左右的数字个数。假设 A,BA,B 中下标小于等于 rr 的都在 ii 右边，那么这种选法对答案的贡献如下： (∑j=1l(i−j+1)−Ar+j)+(∑j=1rBj−(i+j))(\sum_{j=1}^{l}{(i-j+1)-A_{r+j}})+(\sum_{j=1}^{r}{B_j-(i+j)}) 稍加整理，得到下式： (∑j=i−l+1ij−∑j=i+1i+rj−∑j=1mAj)+(∑j=1rAj+Bj)(\sum_{j=i-l+1}^{i}{j}-\sum_{j=i+1}^{i+r}{j}-\sum_{j=1}^{m}{A_j})+(\sum_{j=1}^{r}{A_j+B_j}) 可以发现，如果 A,BA,B 确定了，最终对答案的贡献就是前一个括号里的定值加上前 rr 小的 A+BA+B 的值。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+10,inf=1e11,sgl=-2e11,sgr=2e11;
int n,m;
int w[N],a[N],b[N],suma;
int lst[N],nxt[N];
int root;
struct segmenttree{
	int pcnt;
	struct node{
		int ls,rs,siz,data;
	}t[N<<5];
	void push_up(int p){
		t[p].data=t[t[p].ls].data+t[t[p].rs].data;
		t[p].siz=t[t[p].ls].siz+t[t[p].rs].siz;
	}
	void modify(int l,int r,int x,int &p,int d){
		if(!p){p=++pcnt;t[p].ls=t[p].rs=t[p].data=t[p].siz=0;}
		if(l==r){
			t[p].siz+=d;t[p].data+=d*x;return ;
		}
		int mid=l+r>>1;
		if(mid>=x)modify(l,mid,x,t[p].ls,d);
		else modify(mid+1,r,x,t[p].rs,d);
		push_up(p);
	}
	int query(int l,int r,int p,int k){
		if(!p)return 0;
		if(l==r)return t[p].data/t[p].siz*k;
		int ret=0,mid=l+r>>1;
		if(t[t[p].ls].siz>=k)ret=query(l,mid,t[p].ls,k);
		else ret=query(mid+1,r,t[p].rs,k-t[t[p].ls].siz)+t[t[p].ls].data;
		return ret;
	}
}s;
void push(int a,int b,int d){
	s.modify(sgl,sgr,a+b,root,d);suma+=a*d;
}
int ans=inf;
int Galse(int l,int r){
	if(l>r)return 0;
	return (l+r)*(r-l+1)/2;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)nxt[i]=0;
	for(int i=1;i<=m;i++)a[i]=b[i]=lst[i]=0;
	suma=s.pcnt=root=0;
	ans=inf;
	for(int i=1;i<=n;i++){
		cin>>w[i];
		nxt[lst[w[i]]]=i;
		lst[w[i]]=i;
	}
	for(int i=1;i<=n;i++)if(!nxt[i])nxt[i]=inf;
	for(int i=1;i<=m;i++)a[i]=-inf;
	for(int i=1;i<=n;i++)if(!b[w[i]])b[w[i]]=i;
	for(int i=1;i<=m;i++)push(a[i],b[i],1);
	int l=m/2,r=m-l;
	for(int i=1;i<=n;i++){
		push(a[w[i]],b[w[i]],-1);
		a[w[i]]=b[w[i]];b[w[i]]=nxt[i];
		push(a[w[i]],b[w[i]],1);
		ans=min(ans,Galse(i-l+1,i)-Galse(i+1,i+r)-suma+s.query(sgl,sgr,root,r));
	}
	cout<<ans<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T;cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...