牛客网 - [牛客练习赛49]筱玛爱线段树(差分)

链接：https://ac.nowcoder.com/acm/contest/946/D
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

筱玛是一个热爱线段树的好筱玛。
筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：
给定一个长度为n的数组A，刚开始每一项的值均为0。

支持以下两种操作，操作共m次：

1 l r：将Al∼Ar的每一项的值加上1。
2 l r：执行操作编号在[l,r]内的所有操作各一次，保证r小于当前操作的编号。

m次操作结束后，你要告诉马爷A数组变成什么样子了。
由于答案可能会很大，你只需要输出数组A中的每个数在模10^9+7意义下的值。

输入描述

第一行两个数n,m，分别表示数组长度及操作次数。
接下来m行，每行三个数opt,l,r，表示一次操作。

输出描述

输出一行共n个数，表示m次操作结束后，A1∼An的值。

输入

4 3
1 1 3
2 1 1
1 1 3

输出

3 3 3 0

备注

对于100%的数据，1≤n≤10^5,1≤m≤10^5。

解题思路

维护两个差分数组，一个是重复操作的差分数组，另一个是当前数组A的值的差分数组，对第二个差分数组的每次修改的大小是当前操作重复操作的次数。因为每次第二种操作总是针对当前之前的操作，所以要倒着跑一遍。最后针对A数组的值的差分数组求个前缀和就行了。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
const int MOD = 1e9 + 7;
int n, m;
ll a[N], pre[N];
struct edge {
    int l, r, op;
} e[N];
int main() {
    while (~scanf("%d%d", &n, &m)) {
        memset(a, 0, sizeof(a));
        memset(pre, 0, sizeof(pre));
        pre[m + 1]++;
        pre[0]--;
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &e[i].op, &e[i].l, &e[i].r);
        for (int i = m; i >= 1; i--) {
            pre[i] = (pre[i] + pre[i + 1]) % MOD;
            if (e[i].op != 1) {
                pre[e[i].r] = (pre[e[i].r] + pre[i]) % MOD;
                pre[e[i].l - 1] = (pre[e[i].l - 1] - pre[i] + MOD) % MOD;
            }
            else {
                a[e[i].l] = (a[e[i].l] + pre[i]) % MOD;
                a[e[i].r + 1] = (a[e[i].r + 1] - pre[i] + MOD) % MOD;
            }
        }
        for (int i = 1; i <= n; i++)
            a[i] = (a[i] + a[i - 1]) % MOD;
        for (int i = 1; i <= n; i++)
            printf("%lld%c", a[i], "\n "[i != n]);
    }
    return 0;
}