牛客练习赛49 D 筱玛爱线段树 倒序差分

链接：https://ac.nowcoder.com/acm/contest/946/D
来源：牛客网

题目描述

筱玛是一个热爱线段树的好筱玛。

筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：

给定一个长度为n的数组A，刚开始每一项的值均为0。

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

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​的值。

示例1

输入

4 3
1 1 3
2 1 1
1 1 3

输出

3 3 3 0

备注:

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

题解：

用两个差分数组，一个维护操作次数的差分，一个维护原序列的差分。

 倒着计算，就能计算出每个操作 执行的次数。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int mod=1e9+7;
int s[maxn],L[maxn],R[maxn];
ll a[maxn];
ll b[maxn];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",s+i,L+i,R+i);
    }
    for(int i=m;i;i--){
        b[i]=(b[i]+b[i+1])%mod;
        if(s[i]==1){
            (a[L[i]]+=b[i]+1)%=mod;
            (a[R[i]+1]-=b[i]+1)%=mod;
        }else{
            b[R[i]]+=b[i]+1;
            b[L[i]-1]-=b[i]+1;
        }
    }
    for(int i=1;i<=n;i++){
        a[i]=(a[i]+a[i-1]+mod)%mod;
    }
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
    return 0;
}