abc340E题解

题目描述

样例

input:
5 3
1 2 3 4 5
2 4 0
output:0 4 2 7 2

算法1

(树状数组) $O(nlogn)$

本题我们可以看作对于每一个查询位置x我们都需要先把该位置上的所有球拿出来，然后再一个一个的放到对应位置上去。假设x位置上面有y个球，那么对于这y个球，如果大于n，那么就对所有的位置放y/n个球，然后在对余下的球进行放置。很显然余下的球也存在两种情况。

当x+y%n<=n时，我们仅仅需要对[x+1,x+y%n]的位置放球。
而当我们的x+y%n>n时，我们则需要对面前的[1,(x+y%n)%n]的范围也放球。

那么我们可以发现本题本质上只有三个操作：单点查询，单点修改，区间修改，那么我们很容易想到用一个树状数组维护a[i]的差分序列即可求解。

C++ 代码

#include<bits/stdc++.h>
using i64=long long;
const int N=2e5+5;
int n,m;
i64 c[N];
int lowbit(int x){
    return x&-x;
}
void add(int x,i64 k){
    for(int i=x;i<=n;i+=lowbit(i)){
        c[i]+=k;
    }
}
i64 ask(int x){
    i64 res=0;
    for(int i=x;i;i-=lowbit(i)){
        res+=c[i];
    }
    return res;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin>>n>>m;
    for(int i=1;i<=n;i++){
        i64 x;
        std::cin>>x;
        add(i,x),add(i+1,-x);
    }
    for(int i=1;i<=m;i++){
        int x;
        std::cin>>x;
        x++;
        i64 y=ask(x);
        add(x,-y),add(x+1,y);
        add(1,y/n),add(n+1,-y/n);
        add(x+1,1),add(std::min(n,x+(int)(y%n))+1,-1);
        if(x+y%n>n){
            add(1,1);
            add((x+y%n)%n+1,-1);
        }
    }
    for(int i=1;i<=n;i++){
        std::cout<<ask(i)<<" ";
    }
    return 0;
}