自动搬运

查看原文

来自洛谷，原作者为

	LZDQ **

搬运于2025-08-24 22:33:41，当前版本为作者最后更新于2022-08-10 17:02:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

对于一组询问，我们记 $v$ 为询问希望得到的众数，$x$ 为最后众数出现的次数。这个问题可以用费用流来描述，对坐标离散化并预留足够的溢出位置后，相邻两个点连一条边，$v$ 这个位置向汇点连一条带上下界的边，其他地方连一条带上界的边。于是我们可以得到一个结论，令 $f(x)=y$ 表示答案，则 $f$ 是一个下凸函数。当然不用费用流也可以得到类似的结论。

现在解决给定 $v,x$ 求答案。根据费用流的建模，要让 $x$ 个数变成 $v$，一定可以看作是把最近的 $x$ 个数变成 $v$。所以我们只需要解决对于序列的每个前缀和后缀，需要多少次操作才能使得众数的出现次数不超过 $x$。

考虑根号分治。令块长为 $B$，对于 $x\le B$ 的部分，每个 $x$ 用 $O(n)$ 预处理。对于 $x>B$ 的部分，显然不合法的位置至多有 $\frac nB$ 个，总变化量是 $O(\frac nB)$ 级别的。

我们枚举每个 $x\le B$ 并更新答案。剩下的部分使用二分，二分到最后一个斜率为负的位置，就是最小值。总复杂度 $O(Bn+\frac nB\log n)$，取 $B=\sqrt {n\log n}$ 即可做到 $O(n\sqrt{n\log n})$。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
int n,q,a[MAXN],B,op[MAXN][2];
int all[MAXN],cnt[MAXN],_cnt[MAXN];
ll sum[MAXN];
ll f1[MAXN],g1[MAXN],f2[MAXN],g2[MAXN];
void Solve(int x,ll *f,ll *g){
	int l=0,c=0;
	ll res=0;
	for(int i=1; i<=n; i++){
		while(l<a[i]){
			if(c<=x){
				c=0;
				break;
			}
			c-=x;
			res+=c;
			l++;
		}
		l=a[i];
		c++;
		ll k=c/x;
		f[i]=res+c*k-x*k*(k+1)/2;
	}
	static int sx[MAXN],sy[MAXN],top;
	top=0;
	res=0;
	for(int i=n,j=n+1; i; i--){
		while(j>n||all[j]!=a[i]){
			j--;
			top++;
			sx[top]=all[j];
			sy[top]=0;
		}
		res+=sx[top]-a[i];
		if(++sy[top]==x) top--;
		g[i]=res;
	}
	return ;
}
vector<int> vec;
int chg[MAXN];
ll Calc1(int w,int x){
	if(!w) return 0;
	int _w=lower_bound(a+1,a+n+1,a[w])-a;
	_w=w-_w+1;
	w=lower_bound(all+1,all+n+1,a[w])-all;
	chg[*chg=1]=w;
	cnt[w]=_w;
	ll res=0;
	for(int i=0; i<vec.size(); i++){
		int k=vec[i];
		if(k>=w) break;
		if(cnt[k]>x) chg[++*chg]=k;
		while(k<w&&cnt[k]>x){
			chg[++*chg]=k+1;
			cnt[k+1]+=cnt[k]-x;
			res+=cnt[k]-x;
			cnt[k]=x;
			k++;
		}
	}
	while(cnt[w]>x){
		res+=cnt[w]-x;
		cnt[w]-=x;
	}
	for(int i=1; i<=*chg; i++)
		cnt[chg[i]]=_cnt[chg[i]];
	return res;
}
ll Calc2(int w,int x){
	if(w>n) return 0;
	int _w=upper_bound(a+1,a+n+1,a[w])-a-1;
	_w=_w-w+1;
	w=lower_bound(all+1,all+n+1,a[w])-all;
	chg[*chg=1]=w;
	cnt[w]=_w;
	ll res=0;
	for(int i=lower_bound(vec.begin(),vec.end(),w)-vec.begin(); i<vec.size(); i++){
		int k=vec[i];
		if(cnt[k]>x) chg[++*chg]=k;
		while(cnt[k]>x){
			chg[++*chg]=k+1;
			cnt[k+1]+=cnt[k]-x;
			res+=cnt[k]-x;
			cnt[k]=x;
			k++;
		}
	}
	for(int i=1; i<=*chg; i++)
		cnt[chg[i]]=_cnt[chg[i]];
	return res;
}
bool vis[MAXN];
ll ans[MAXN];
int main(){
	scanf("%d%d",&n,&q);
	B=min(800,n);
	for(int i=1; i<=n; i++)
		scanf("%d",a+i);
	if(n==1){
		while(q--){
			int x;
			scanf("%d",&x);
			if(x>=a[1]) printf("%d\n",x-a[1]);
			else puts("-1");
		}
		return 0;
	}
	sort(a+1,a+n+1);
	for(int i=1; i<=n; i++)
		all[i]=max(all[i-1]+1,a[i]),sum[i]=sum[i-1]+a[i];
	for(int i=1,j=1; i<=n; i++){
		while(all[j]!=a[i]) j++;
		cnt[j]++;
	}
	for(int i=1; i<=n; i++)
		if(cnt[i]>B) vec.push_back(i);
	memcpy(_cnt,cnt,sizeof(cnt));
	Solve(B,f1,g1);
	Solve(B-1,f2,g2);
	for(int i=1; i<=q; i++){
		scanf("%d",op[i]);
		int v=op[i][0];
		int w=upper_bound(a+1,a+n+1,v)-a-1,x;
		op[i][1]=w;
		if(w>=B){
			x=B;
			ll y1=f1[w-x]+g1[w+1]+(1ll*v*x-(sum[w]-sum[w-x]));
			x--;
			ll y2=f2[w-x]+g2[w+1]+(1ll*v*x-(sum[w]-sum[w-x]));
			if(y1>=y2) vis[i]=1,ans[i]=-1;
			else{
				int l=B,r=w;
				while(l<r){
					int mid=l+r>>1;
					x=mid;
					y1=Calc1(w-x,x)+Calc2(w+1,x)+(1ll*v*x-(sum[w]-sum[w-x]));
					x++;
					y2=Calc1(w-x,x)+Calc2(w+1,x)+(1ll*v*x-(sum[w]-sum[w-x]));
					if(y1<y2) r=mid;
					else l=mid+1;
				}
				x=l;
				ans[i]=Calc1(w-x,x)+Calc2(w+1,x)+(1ll*v*x-(sum[w]-sum[w-x]));
			}
		}else vis[i]=1,ans[i]=-1;
	}
	for(int x=1; x<=B; x++){
		Solve(x,f1,g1);
		bool ok=0;
		for(int i=1; i<=q; i++)
			if(vis[i]){
				int v=op[i][0],w=op[i][1];
				if(x>w){
					vis[i]=0;
					continue;
				}
				ll y=f1[w-x]+g1[w+1]+(1ll*v*x-(sum[w]-sum[w-x]));
				if(x>1&&y>=ans[i]){
					vis[i]=0;
					continue;
				}
				ans[i]=y;
				ok=1;
			}
		if(!ok) break;
	}
	for(int i=1; i<=q; i++)
		printf("%lld\n",ans[i]);
	return 0;
}

之前写挂的原因：复制了一行代码忘改一点东西，两个函数对着写，结果第二个函数写反了。改进行修改的没修改。q 写成 n。总结：千万不要复制代码，总是忘改东西，也不要对着之前的代码写。