题意:
一个长度为n的数组,初始值都是0,给出2个操作:
操作1: 区间[l:r] 加1
操作2: 执行操作编号在[l,r]内的所有操作各一次

求最后序列是多少?

分析:
1、首先操作2是在之前操作再进行一次,所以我们可以先统计当前这个位置被操作了多少次,怎么统计呢,每个2的操作是对前面操作的重复,
所以我们把操作从后往前跑,维护差分数组,求后缀和。

2、其次我们计算答案的时候,也是维护差分数组。最后答案就是前缀和跑一下。

详细看代码:

#include <bits/stdc++.h>

#define int long long 

using namespace std;

const int mod=1e9+7;

const int N=1e5+100;

int n,m;
int op;

struct Node
{
    int op,l,r;
}q[N];

int cnt[N];
int ans[N];

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&q[i].op,&q[i].l,&q[i].r);
    }
    cnt[m+1]=1;
    for(int i=m;i>=1;i--)
    {
        cnt[i]=(cnt[i]+cnt[i+1])%mod;
        int l=q[i].l;
        int r=q[i].r;
        if(q[i].op==2)
        {
            cnt[r]=(cnt[r]+cnt[i])%mod;
            cnt[l-1]=(cnt[l-1]-cnt[i]+mod)%mod;
        }
    }
//    for(int i=1;i<=m;i++)
//    {
//        printf("%d%c",cnt[i]," \n"[i==m]);
//    }
    for(int i=1;i<=m;i++)
    {
        int l=q[i].l;
        int r=q[i].r;
        if(q[i].op==1)
        {
            ans[l]=(ans[l]+cnt[i])%mod;
            ans[r+1]=(ans[r+1]-cnt[i]+mod)%mod;
        }
    }

    for(int i=1;i<=n;i++)
    {
        ans[i]=(ans[i]+ans[i-1])%mod;
        printf("%lld%c",ans[i]%mod," \n"[i==n]);
    }
    return 0;
}