AtCoder Beginner Contest 340 E - Mancala 2 题解

题意

有编号为 $0$ 到 $N-1$ 的 $N$ 个盒子。最初，盒子 $i$ 里有 $A_i$ 个球。

高桥君将按顺序对 $i=1,2,\ldots,M$ 执行以下操作：

• 将一个变量 $C$ 设置为 $0$。
• 从盒子 $B_i$ 中取出所有球并拿在手里。
• 当手里至少还有一个球时，重复以下过程：
  将 $C$ 的值增加 $1$。
  将手里的一个球放入盒子 $(B_i+C) \bmod N$ 中。

在完成所有操作后，确定每个盒子中的球数。

思路

题面中的操作可以被转化为以下步骤：

• 把位置 $i$ 的值归零；
• 将整个序列的值增加 $\lfloor\frac{A_i}{N}\rfloor$；
• 将 $(i,\min(i+A_i\mod N,N)]$ 的值增加 $1$；
• 如果 $i+A_i\mod N>N$，再将 $[1,i+A_i\mod N-N]$ 的值增加 $1$。

于是我们可以直接用数据结构维护，建立一棵支持区间加，单点查询的线段树直接模拟操作即可，时间复杂度 $M \log N$。
注意有一些细节需要注意：

• 输入给的下标 $B_i$ 从 $0$ 开始，预处理时需要 $+1$；
• 如果 $B_i=N$，需要跳过第三步操作，否则会越界。

代码

const int N = 2e5+5;
ll a[N];
int b[N];

struct seg{
    ll mark,val;
    int l,r;
    seg(){mark = 0,val = 0;}
    inline int size(){return r-l+1;}
};

struct segTree{
    seg tree[N*4];
    inline void pushup(int p){tree[p].val = tree[p<<1].val+tree[(p<<1)+1].val;}
    inline void pushdown(int p){
        if(tree[p].mark){
            tree[p<<1].mark+=tree[p].mark;tree[(p<<1)+1].mark+=tree[p].mark;
            tree[p<<1].val+=tree[p].mark*tree[p<<1].size();tree[(p<<1)+1].val+=tree[p].mark*tree[(p<<1)+1].size();
            tree[p].mark = 0;
        }
    }
    void build(int l,int r,int p){
        tree[p].l = l;tree[p].r = r;
        if(l==r){
            tree[p].val = a[l];
        }
        else{
            int mid = (l+r)>>1;
            build(l,mid,p<<1);
            build(mid+1,r,(p<<1)+1);
            pushup(p);
        }
    }
    void add(int l,int r,int nl,int nr,int p,ll val){
        if(nl>=l && nr<=r){
            tree[p].val+=tree[p].size()*val;
            if(nl!=nr)	tree[p].mark+=val;
        }
        else{
            int mid = (nl+nr)>>1;
            pushdown(p);
            if(mid>=l)	add(l,r,nl,mid,p<<1,val);
            if(mid+1<=r)	add(l,r,mid+1,nr,(p<<1)+1,val);
            pushup(p);
        }
    }
    void update(int d,int l,int r,int p,ll val){
        if(d==l && l==r)	tree[p].val = val;
        else{
            int mid = (l+r)>>1;
            pushdown(p);
            if(mid>=d)	update(d,l,mid,p<<1,val);
            else update(d,mid+1,r,(p<<1)+1,val);
            pushup(p);
        }
    }
    ll query(int l,int r,int nl,int nr,int p){
        if(nl>=l && nr<=r)	return tree[p].val;
        else{
            ll now = 0;
            pushdown(p);
            int mid = (nl+nr)>>1;
            if(mid>=l)	now+=query(l,r,nl,mid,p<<1);
            if(mid+1<=r)	now+=query(l,r,mid+1,nr,(p<<1)+1);
            return now;
        }
    }
}Tree1;    //线段树

int n,m;

void print_ans(){
    for(int i=1;i<=n;i++){
        cout<<Tree1.query(i,i,1,n,1)<<" ";
    }
    cout<<"\n";
}    //输出答案

void work(int x){    //注意操作细节
    ll now = Tree1.query(b[x],b[x],1,n,1);
    Tree1.update(b[x],1,n,1,0);
    ll d = now/n;
    Tree1.add(1,n,1,n,1,d);
    ll k = now%n;
    if(k){
        if(k<=n-b[x]){
            Tree1.add(b[x]+1,b[x]+k,1,n,1,1);
        }
        else{
            if(b[x]<n){
                Tree1.add(b[x]+1,n,1,n,1,1);
                k-=(n-b[x]);
            }
            Tree1.add(1,k,1,n,1,1);
        }
    }
}

void solve(){
    read(n);read(m);
    for(int i=1;i<=n;i++)	read(a[i]);
    Tree1.build(1,n,1);
    for(int i=1;i<=m;i++){
        read(b[i]);
        b[i]++;
    }
    for(int i=1;i<=m;i++){
        work(i);
        // print_ans();
    }
    print_ans();
}

int main(){
    int t = 1;
//    read(t);
    for(int tt=1;tt<=t;tt++){
        solve();
    }
}