筱玛爱线段树（差分数组）

题目：

给定一个长度为 $n$ 的数组 $A$ ，刚开始每一项的值均为0。 $m$ 个操作：
1 l r：数组A中 $[l,r]$ 区间的数+1。
2 l r： $[l,r]$ 区间的操作重做一遍。（数据保证 $r$ 小于当前操作编号） $m$ 次操作后，输出数组 $A$ 。 $mod$ 1e9+7输出。
$n、m≤1e5。$

做法：

由于2操作不会直接作用在数组 $A$ 上。所以我们的关注点在于 $m$ 个操作中所有1操作对应的次数。如果我们知道每个1操作做了几次，设 $cnt[i]$ 为第 $i$ 个操作的次数，那么差分一下就能得到数组 $A$ 了，具体就是1到m $for$ 一遍，对所有1操作 $A[l] += cnt[i],A[r+1] -= cnt[i]$ ,然后做一次前缀和。
题目告诉我们2操作只会影响前面操作的次数。所以我们从后往前处理，同样用一次差分就能得到 $cnt[]$ 数组，具体就是m到1 $for$ 一遍，对所有的2操作， $cnt[r] += cnt[i],cnt[l-1] -= cnt[i]$ ,因为差分要用到 $cnt[i]$ ,所以做差分的同时做 $cnt[]$ 的后缀和。
所以总共是做2次差分解决问题。
写得没有很清晰。大家可以看看代码理解一下。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
struct node{
    int op, l, r;
    node(){}
    node(int op, int l, int r):op(op),l(l),r(r){}
}q[N];
ll a[N], b[N];
int main(void){
    IOS;
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int op, l, r; cin >> op >> l >> r;
        q[i] = node(op, l, r);
    }
    a[m+1] = 1;
    for (int i = m; i >= 1; --i){
        int op = q[i].op, l = q[i].l, r = q[i].r;
        a[i] = (a[i]+a[i+1])%mod;
        if (op == 2) a[r] = (a[r]+a[i])%mod, a[l-1] = ((a[l-1]-a[i])%mod+mod)%mod;
    }
    for (int i = 1; i <= m; ++i){
        int op = q[i].op, l = q[i].l, r = q[i].r;
        if (op == 1) b[l] = (b[l]+a[i])%mod, b[r+1] = ((b[r+1]-a[i])%mod+mod)%mod;
    }
    for (int i = 1; i <= n; ++i){
        b[i] = (b[i]+b[i-1])%mod;
        cout << b[i] << ' ';
    }
    return 0;
}