欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-12 17:38:55
...

链接: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;
}