【2022 NOIP 模拟赛 38】数环 做题记录

小 A 有 $n$ 个数绕成一个环，他们分别是 $a_1,a_2,\cdots,a_n$。

每一轮，小A可以选择某个数 $a_i$， 把它变成 $-a_i$，并让两个相邻的数加上 $a_i$。

小 A 想知道，她最少经过几轮操作可以让所有的数都是非负整数呢？

$2\le n\le 10^5$，$0\le |a_i|\le 10^5$。

不考虑环的限制，考虑在序列上的情况。不难发现，这样一次操作的本质其实是交换了相邻两个位置的前缀和，所以设 $sum_i$ 为 $\sum\limits_{j=1}^ia_j$ 则一次操作为交换 $sum_i,sum_{i+1}$，目标即为让所有 $sum_i\ge0$ 并且对于所有 $1\le i\le n-1$ 有 $sum_i\le sum_{i+1}$。

考虑这个性质拓展到环上，我们把原序列复制无数次，钦定某个位置的前缀和为 $0$，并求出整个序列的前缀和 $sum_i$：

这样一次操作就相当于交换所有满足 $x\operatorname{mod}n=i$ 的 $sum_x$ 和 $sum_{x+1}$：

考虑固定 $n-1$ 这个位置，即以它为参照系，假定它不会移动，那么交换中间那些前缀和肯定没有影响，考虑操作 $i=n-1$ 的情况：

这里平移了是因为我们认为 $n-1$ 是不动的，那么操作就变成了把 $sum_0$ 加上 $sum_{n-1}$ 然后放到 $n-1$ 的前面。

同理，操作 $i=n-2$ 就相当于把 $sum_{n-2}$ 减去 $sum_{n-1}$，然后放到最前面：

那么有个显然的贪心策略：把所有 $sum_i<0$ 和 $sum_i>sum_{n-1}$ 的 $sum_i$ 都通过不断减去 $sum_{n-1}$ 使得 $0\le sum_i\le sum_{n-1}$，最后再通过交换来排序。

直接做不好维护，不妨先把 $sum_i<0$ 的换到最前面，$sum_i>sum_{n-1}$ 的换到最后面，这样一定不会让答案变大。然后考虑贪心：

• 显然先处理 $sum_i<0$ 的再处理 $sum_i>sum_{n-1}$ 的是最优的；
• 绕圈的时候不“超车”是最优的；

那么用树状数组维护即可，可以结合代码理解：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

inline void fio(string name)
{
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

const int S=1000005;

int n,a[S];
long long s,ans,sum[S],b[S];
int c[S];
long long c2[S];
long long ned[S],nxt[S];
int id[S];

inline void add(int pos)
{
	for(int i=pos;i<=n;i+=i&-i) c[i]++;
}

inline int que(int pos)
{
	int res=0;
	for(int i=pos;i>=1;i-=i&-i) res+=c[i];
	return res;
}

inline void add2(int pos,long long val)
{
	for(int i=pos;i<=n;i+=i&-i) c2[i]+=val;
}

inline long long que2(int pos)
{
	long long res=0;
	for(int i=pos;i>=1;i-=i&-i) res+=c2[i];
	return res;
}

inline bool cmp1(int x,int y)
{
	int tpex=sum[x]<0?0:(sum[x]<=s?1:2);
	int tpey=sum[y]<0?0:(sum[y]<=s?1:2);
	if(tpex!=tpey) return tpex<tpey;
	return x<y;
}

inline bool cmp2(int x,int y)
{
	int tpex=sum[x]<0?2:(sum[x]<=s?1:0);
	int tpey=sum[y]<0?2:(sum[y]<=s?1:0);
	if(tpex!=tpey) return tpex<tpey;
	if(ned[x]!=ned[y]) return tpex==2?ned[x]<ned[y]:ned[x]>ned[y];
	else return x<y;
}

inline void slove()
{
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
	s=sum[n],ans=0;
	if(s==0)
	{
		for(int i=1;i<=n;i++) if(sum[i]!=0) return void(puts("-1"));
		return void(puts("0"));
	}
	if(s<0) return void(puts("-1"));
	for(int i=1;i<=n-1;i++) id[i]=i;
	sort(id+1,id+n,cmp1);
	for(int i=1;i<=n-1;i++) nxt[i]=sum[id[i]];
	for(int i=1;i<=n-1;i++) sum[i]=nxt[i];
	for(int i=1;i<=n;i++) c[i]=0;
	for(int i=n-1;i>=1;i--)
	{
		ans+=que(id[i]-1);
		add(id[i]);
	}
	for(int i=1;i<=n-1;i++)
	{
		if(sum[i]<0) ned[i]=(-sum[i]+s-1)/s;
		else if(sum[i]<=s) ned[i]=0;
		else ned[i]=(sum[i]-1)/s;
	}
	int cntsm=0,cntbg=0;
	for(int i=1;i<=n-1;i++) cntsm+=sum[i]>=0,cntbg+=sum[i]<=s;
	for(int i=1;i<=n-1;i++) b[i]=ned[i];
	sort(b+1,b+n);
	int m=unique(b+1,b+n)-b-1;
	for(int i=1;i<=n;i++) c[i]=c2[i]=0;
	for(int i=1;i<=n-1;i++)
	{
		if(sum[i]<0)
		{
			int id=lower_bound(b+1,b+m,ned[i])-b;
			add(id),add2(id,ned[i]);
			int sm=upper_bound(b+1,b+m,ned[i]-1)-b-1;
			ans+=ned[i]*que(sm)-que2(sm)+(ned[i]-1)*cntsm+ned[i]+n-1-cntbg;
		}
	}
	for(int i=1;i<=n;i++) c[i]=c2[i]=0;
	for(int i=n-1;i>=1;i--)
	{
		if(sum[i]<0)
		{
			int id=lower_bound(b+1,b+m,ned[i])-b;
			add(id),add2(id,ned[i]);
			int sm=upper_bound(b+1,b+m,ned[i]-1)-b-1;
			ans+=(ned[i]-1)*que(sm)-que2(sm);
		}
	}
	for(int i=1;i<=n;i++) c[i]=c2[i]=0;
	for(int i=n-1;i>=1;i--)
	{
		if(sum[i]>s)
		{
			int id=lower_bound(b+1,b+m,ned[i])-b;
			add(id),add2(id,ned[i]);
			int sm=upper_bound(b+1,b+m,ned[i]-1)-b-1;
			ans+=ned[i]*que(sm)-que2(sm)+(ned[i]-1)*cntbg+ned[i];
		}
	}
	for(int i=1;i<=n;i++) c[i]=c2[i]=0;
	for(int i=1;i<=n-1;i++)
	{
		if(sum[i]>s)
		{
			int id=lower_bound(b+1,b+m,ned[i])-b;
			add(id),add2(id,ned[i]);
			int sm=upper_bound(b+1,b+m,ned[i]-1)-b-1;
			ans+=(ned[i]-1)*que(sm)-que2(sm);
		}
	}
	for(int i=1;i<=n-1;i++) nxt[i]=sum[i]<0?sum[i]+s*ned[i]:sum[i]-s*ned[i];
	for(int i=1;i<=n-1;i++) id[i]=i;
	sort(id+1,id+n,cmp2);
	for(int i=1;i<=n-1;i++) b[i]=sum[i]=nxt[id[i]];
	sort(b+1,b+n);
	for(int i=1;i<=n;i++) c[i]=0;
	for(int i=n-1;i>=1;i--)
	{
		int id=lower_bound(b+1,b+n,sum[i])-b;
		ans+=que(id-1);
		add(id);
	}
	printf("%lld\n",ans);
}

int main()
{
	fio("elasticity");
	while(1)
	{
		scanf("%d",&n);
		if(n==0) break;
		slove();
	}
	return 0;
}