本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-10 22:08:18

题意

有 $n$ 盒球（编号从 $0$ 开始），第 $(n-1)$ 个盒的下一个盒为第 $0$ 个，每盒初始有一些球。每次拿出一个盒内的所有球，从该盒开始不断向下一个盒放一个球，放完为止，求最终每盒内的球数。

思路

本题有显然的模拟解法，但 $A_i$ 过大，时间复杂度过高，无法通过本题。

我们发现时间复杂度的瓶颈在于模拟放球，此处可以使用线段树优化区间加操作。

（以下设取出的球数为 $S$）

当 $S$ 较大时，每个盒子至少会被加上 $\lfloor \frac{S}{n} \rfloor$ 个球，也就是至少会把 $n$ 个盒子全部放 $\lfloor \frac{S}{n} \rfloor$ 遍。

发现这里的多次放球可以转化为放多个球，便可以用一次区间加解决。

因此先对全部盒子进行一次区间加处理，同时令 $S$ 对 $n$ 取模，如此可以保证没有重复加球的盒子。

之后使用线段树进行区间加 $1$，最后输出答案即可。

此处需要注意剩余的区间可能会从第 $(n-1)$ 个盒子跳到第 $1$ 个盒子，需要特判成两个区间分别进行维护。

具体操作请看代码实现。

代码

注：本题需要实现区间修改和单点查询，但单点就是长度为 $1$ 的区间，因此笔者写了区间查询。

#include<iostream>
#define int long long
using namespace std;
const int N=2e5+10;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; if(ch==EOF) return 0; ch=getchar();}
	while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int n,m,t=1;
int aa[N]; 
struct nod
{
	int w,l,r,tag;
}a[N*2];\/\/线段树记得开两倍空间 
void pushup(int u)
{
	a[u].w=a[a[u].l].w+a[a[u].r].w;
}
void pushdown(int u,int l,int r)
{
	int mid=(l+r)\/2,lc=a[u].l,rc=a[u].r;
	a[lc].tag+=a[u].tag;
	a[rc].tag+=a[u].tag;
	a[lc].w+=a[u].tag*(mid-l+1);
	a[rc].w+=a[u].tag*(r-mid);
	a[u].tag=0;
} 
void build(int u,int l,int r)
{
	if(l==r)
	{
		a[u].w=aa[l];
		return;
	}
	int mid=(l+r)\/2;
	a[u].l=++t;
	build(t,l,mid);
	a[u].r=++t;
	build(t,mid+1,r);
	pushup(u);
}\/\/建树 
void add(int u,int l,int r,int ll,int rr,int k)
{
	if(l>=ll&&r<=rr)
	{
		a[u].tag+=k;
		a[u].w+=k*(r-l+1);
		return;
	}
	pushdown(u,l,r);
	int mid=(l+r)\/2;
	if(ll<=mid)
		add(a[u].l,l,mid,ll,rr,k);
	if(rr>mid)
		add(a[u].r,mid+1,r,ll,rr,k);
	pushup(u);
}\/\/对ll-rr区间加 
int check(int u,int l,int r,int ll,int rr)
{
	if(l>=ll&&r<=rr)
		return a[u].w;
	int mid=(l+r)\/2,ans=0;
	pushdown(u,l,r);
	if(ll<=mid)
		ans+=check(a[u].l,l,mid,ll,rr);
	else
		ans+=check(a[u].r,mid+1,r,ll,rr);
	return ans;
}\/\/查询ll-rr区间和 
signed main()
{
	n=read(),m=read();
	for(int i=0;i<n;i++)
		aa[i]=read();
	build(1,0,n-1);
	for(int i=1;i<=m;i++)
	{
		int tu=read();
		int ts=check(1,0,n-1,tu,tu);\/\/取出的球数 
		add(1,0,n-1,tu,tu,-ts);\/\/取球操作 
		int sum=ts\/n;\/\/每个盒子放一遍的轮数 
		if(sum>0)
			add(1,0,n-1,0,n-1,sum);
		ts%=n;\/\/处理该情况
		if(ts==0)
			continue;\/\/如果已经放完了就结束 
		if(tu+ts>n-1)
		{
			if(tu!=n-1)
				add(1,0,n-1,tu+1,n-1,1);
			ts-=(n-1-tu),tu=-1;
		}\/\/若出现两个区间则先将以(n-1)为结尾的区间处理完，转到另一个以1开头的区间 
		tu++;
		add(1,0,n-1,tu,tu+ts-1,1);\/\/对剩余区间操作 
	}
	for(int i=0;i<n;i++)
		cout<<check(1,0,n-1,i,i)<<' '; \/\/输出 
	return 0;
}