ABC340E 题解

· · 题解

题意

有 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;
}