题解 | 小w的糖果

一共有n个人，他们排成一列，现在要给他们发糖果，有三种发放方式

1. 从位置p开始一直到n，每个人都发一个
2. 从位置p开始一直到n，第一个人发1个，第二个人发2个，以此类推
3. 从位置p开始一直到n，第一个人发1^2个，第二个人发个，第三个人发个，以此类推

给出若干次发放及其起始位置，问在这些发放结束以后，每个人的糖果数量

• 设置三个数组a,b,c，分别代表这三个操作给每个位置带来的糖果增量，显然答案应该是它们的和，那么对于第一个操作，如果从p位置开始，那么a[p] += 1，那么其他位置的增量就可以用一次前缀和来得到，因为p位置之后的它们都一样；对于第二个操作，同样是b[p] += 1，那么其他位置的增量如何表示呢？应该是b数组的前缀和再求一次前缀和，第一次前缀和是把p位置的修改带来的影响传递下去，第二次前缀和是统计这些影响带来的糖果总增量；对于第三个操作，我们还是先c[p] += 1，统计的时候，我们求一次前缀和，传递下去影响，接下来再求一次前缀和，这个时候得到的应该是1,2,3,4...这样一组数，再求前缀和，得到1,3,6,10...这时候我们把，就可以得到，对于这一步操作，为了防止覆盖，要从后往前遍历

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 100;
ll a[MAXN], b[MAXN], c[MAXN];
const int MOD = 1e9 + 7;
int main(){
    int t, n, m, type, pos;
    cin >> t;
    while(t--){
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        memset(c, 0, sizeof c);
        cin >> n >> m;
        while(m--){
            cin >> type >> pos;
            if(type == 1) a[pos]++;
            else if(type == 2) b[pos]++;
            else c[pos]++;
        }
        for(int i=1;i<=n;i++){
            a[i] += a[i - 1];
            b[i] += b[i - 1];
            c[i] += c[i - 1];
            if(a[i] >= MOD) a[i] %= MOD;
            if(b[i] >= MOD) b[i] %= MOD;
            if(c[i] >= MOD) c[i] %= MOD;
        }
        for(int i=1;i<=n;i++){
            b[i] += b[i - 1];
            c[i] += c[i - 1];
            if(b[i] >= MOD) b[i] %= MOD;
            if(c[i] >= MOD) c[i] %= MOD;
        }
        for(int i=1;i<=n;i++){
            c[i] += c[i - 1];
            if(c[i] >= MOD) c[i] %= MOD;
        }
        for(int i=n;i>=1;i--){
            c[i] += c[i - 1];
            if(c[i] >= MOD) c[i] %= MOD;
        }
        for(int i=1;i<=n;i++){
            if(i != 1) cout << ' ';
            cout << (a[i] + b[i] + c[i]) % MOD;
        }
        cout << '\n';
    }
    return 0;
}