专题班前缀和练习题 - H - 小w的糖果

前缀和差分不再过多介绍
这个题思路是在一维数组上多做几阶差分
然后就可以把原数组在 O(n) 的维护，转化成为在差分数组上 O(1) 的维护
做了几阶差分，在求前缀和的时候，就求几次，就 ok 了

type 1的差分：
0 0 0 1 1 1 1 1
0 0 0 1 0 0 0 0

type 2的差分：
0 0 0 1 2 3 4 5
0 0 0 1 1 1 1 1
0 0 0 1 0 0 0 0

type 3的差分：
0 0 0 1 4 9 16 25
0 0 0 1 3 5 7 9
0 0 0 1 2 2 2 2
0 0 0 1 1 0 0 0

这个题就友好在，所有的操作都是在[?,n] 的区间上的，意味着只有左端点需要修改，而右端点是到终点的，不需要对左端点修改操作做一个反向的取消操作来消除影响。
可以看到：
一个常数 <=> 0 次多项式 <=> 做一阶差分
1,2,3,4,5 <=> y = x => 1 次多项式 <=> 做两阶差分
1,4,9,16,25 <=> 2次多项式 <=> 做三阶差分
回归到一般式子

这个式子，做 n + 1 阶差分，也可以变成 O(1) 级别维护
最后再做 n + 1 阶前缀和，也就还原了
想明白数学原理，代码倒是很简单

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const long long MOD = 1e9 + 7;
const int maxn = 1e5 + 10;

int T, n, m;
int ty, pos;
long long d1[maxn], d2[maxn], d3[maxn];

void pre_sum(long long a[]){
    for(int i = 1; i <= n; i++)
        a[i] = (a[i] + a[i - 1]) % MOD;
}

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    while(T--){
        memset(d1, 0, sizeof(d1));
        memset(d2, 0, sizeof(d2));
        memset(d3, 0, sizeof(d3));
        scanf("%d%d", &n, &m);
        while(m--){
            scanf("%d%d", &ty, &pos);
            if (ty == 1) d1[pos]++;
            else if (ty == 2) d2[pos]++;
            else if (ty == 3) d3[pos]++, d3[pos+1]++;
        }
        pre_sum(d1);
        for(int i = 1; i <= 2; i++) pre_sum(d2);
        for(int i = 1; i <= 3; i++) pre_sum(d3);
        for(int i = 1; i <= n; i++)
            printf("%lld%c", (d1[i] + d2[i] + d3[i]) % MOD, i == n ? '\n' : ' ');
    }
    return 0;
}