牛客 练习赛49 D 筱玛爱线段树 [差分 思维]

D 筱玛爱线段树 > 41255996
筱玛是一个热爱线段树的好筱玛。
筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：
给定一个长度为的数组，刚开始每一项的值均为0。
支持以下两种操作，操作共次：
1 l r：将的每一项的值加上1。
2 l r：执行操作编号在内的所有操作各一次，保证小于当前操作的编号。
次操作结束后，你要告诉马爷数组变成什么样子了。
由于答案可能会很大，你只需要输出数组中的每个数在模意义下的值。

越后面的数据 贡献是1
前面对后面的影响更大 倒序 处理前面的后面的影响 用差分记录 这个区间对后面可以有多少影响
f 数组 存操作次数差分序列 c是源序列差分序列

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int n, m;
int c[maxn], f[maxn];
struct node {
    int op, l, r;
}que[maxn];
 
int main() {
    fastio;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
       cin >> que[i].op >> que[i].l >> que[i].r;
    f[m] = 1;
    for(int i = m; i; i --) {
        f[i] = (f[i] + f[i + 1]) % mod;
        if(que[i].op == 1) {
            c[que[i].l] = (c[que[i].l] + f[i]) % mod;
            c[que[i].r + 1] = (c[que[i].r + 1] + mod - f[i]) % mod;
        } else {
            f[que[i].r] = (f[que[i].r] + f[i]) % mod;
            f[que[i].l - 1] = (f[que[i].l - 1] + mod - f[i]) % mod;
        }
    }
    for(int i = 1; i <= n; i ++) {
        c[i] = (c[i - 1] + c[i]) % mod;
        cout << c[i] << " ";
    }
    return 0;
}