牛客练习赛49 D筱玛爱线段树 后缀差分

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

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

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

给定一个长度为nn的数组AA，刚开始每一项的值均为00。

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

1 l r1 l r：将Al∼ArAl∼Ar的每一项的值加上11。

2 l r2 l r：执行操作编号在[l,r][l,r]内的所有操作各一次，保证rr小于当前操作的编号。

mm次操作结束后，你要告诉马爷AA数组变成什么样子了。

由于答案可能会很大，你只需要输出数组AA中的每个数在模109+7109+7意义下的值。

输入描述:

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

输出描述:

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

示例1

输入

复制

4 3
1 1 3
2 1 1
1 1 3

输出

复制

3 3 3 0

备注:

对于100%的数据，1≤n≤105,1≤m≤1051≤n≤105,1≤m≤105。

后缀差分可太秀了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100005;
ll mod=1e9+7;
ll qpow(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1)
            ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}

int choice[maxn];
int l[maxn];
int r[maxn];
ll tp[maxn];//操作次数的后缀差分序列
ll ans[maxn];//答案的后缀差分序列

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&choice[i],&l[i],&r[i]);
    }
    for(int i=m;i>=1;i--)
    {
        if(choice[i]==1)
        {
            tp[i]=(tp[i]+tp[i+1]);//得到第i次操作的操作次数
            tp[i]%=mod;
            ans[l[i]-1]+=mod-tp[i]-1;
            ans[l[i]-1]%=mod;
            ans[r[i]]+=tp[i]+1;
            ans[r[i]]%=mod;
        }
        else if(choice[i]==2)
        {
            tp[i]=tp[i]+tp[i+1];//得到第i次操作的操作次数
            tp[i]%=mod;
            tp[l[i]-1]+=mod-(tp[i]+1);
            tp[l[i]-1]%=mod;
            tp[r[i]]+=(tp[i]+1);
            tp[r[i]]%=mod;
        }
    }
    for(int i=n;i>=1;i--)
    {
        ans[i]=ans[i]+ans[i+1];
        ans[i]%=mod;
    }
    for(int i=1;i<=n;i++)
        printf("%lld ",ans[i]);
}

/*
4 4
1 1 1
2 1 1
2 1 2
2 1 3
*/