自动搬运

查看原文

来自洛谷，原作者为

	Twig_K Life will be easier when the sunlight in

搬运于2025-08-24 23:12:16，当前版本为作者最后更新于2025-04-07 12:44:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

cnblogs

有 $n$ 个整数，值域 $[1,n]$。请你将这 $n$ 个数划分为两个非空集合 $S,T$，并选择 $x,y$。

要求 $x$ 为 $S$ 的众数之一，$y$ 为 $T$ 的众数之一。最大化 $\lvert x-y \rvert$ 的值。

$Q$ 组询问，每次询问前修改 $a_x \leftarrow y$。 $n \leq 2\times 10 ^5$。

题解

对于选出的 $x,y$，考虑如何贪心地划分集合：所有数 $x$ 放入 $S$，所有数 $y$ 放入 $T$，其他数摊到两个集合。

所以，$(x,y)$ 能被同时取出，当且仅当：

即:

既然要最大化下标差，那么我们可以对每种不同的 $cnt$ 记录 $cnt_i=v$ 的最大、最小下标 $mxi_v,mni_v$。

双指针，枚举 $cnt_y$，找到最大的 $cnt_x$ 使 $cnt_x \geq mxcnt - cnt_y$，用 $mxi_{cnt},mni_{cnt}$ 之差更新答案。

双指针移动 $n$ 次，这样复杂度是 $O(n)$ 的，多组询问总复杂度 $O(nQ)$。

怎么优化呢？因为始终有 $\sum cnt_i=n$，所以本质不同的 $cnt_i$ 最多有 $O(\sqrt n)$ 种（考虑 $1+2+ \cdots + t \leq n$ 那么 $t$ 是 $O(\sqrt n)$ 的）。

所以只需要考虑那些不同的非零 $cnt_i$ 即可，用 set 维护存在的 $cnt$ 值，再对每种 $cnt$ 开一个 set 辅助求解最大、最小下标。

时间复杂度 $O(n \log n + n \sqrt n)$。

代码

完整代码

int n,Q;
set<int> st[maxn],S;
int a[maxn],c[maxn],mxi[maxn],mni[maxn];

void addc(int i,int cl){ //i 的得票变成 cl 了
	if(!cl) return; st[cl].insert(i);
	mxi[cl]=max(mxi[cl],i);
	mni[cl]=min(mni[cl],i);
	if(st[cl].size()==1) S.insert(cl);
}
void delc(int i,int cl){ //i 的得票不再是 cl 了
	if(!cl) return; st[cl].erase(i);
	if(st[cl].empty()) S.erase(cl),mxi[cl]=0,mni[cl]=n+1;
	else if(!st[cl].empty()) mxi[cl]=*--st[cl].end(),mni[cl]=*st[cl].begin();
}
signed main()
{
	rd(n),rd(Q);
	For(i,1,n) rd(a[i]),c[a[i]]++,mxi[i]=0,mni[i]=n+1;
	For(i,1,n) addc(i,c[i]);
	while(Q--)
	{
		int i,x;rd(i),rd(x);
		delc(a[i],c[a[i]]--),addc(a[i],c[a[i]]); a[i]=x;
		delc(a[i],c[a[i]]++),addc(a[i],c[a[i]]);
		
		int mx=*--S.end(),mxp=0,mnp=n+1,res=0;
		if(*S.begin()+*S.begin()>=mx) res=max(res,mxi[*S.begin()]-mni[*S.begin()]);
		for(auto itl=S.begin(),itr=--S.end();itl!=S.end();itl++){//双指针
			while(itr!=S.begin() && (*itr)+(*itl)>=mx)
				mxp=max(mxp,mxi[*itr]),mnp=min(mnp,mni[*itr]),itr--;
			res=max(res,max(mxp-mni[*itl],mxi[*itl]-mnp));
		}
		write(res),End;
	}
	return 0;
}