分析

我们主要考虑如何处理 的操作又重新做一次，这个我们考虑区间加，定义 为第 次操作要执行的次数。那么这个我们可以通过差分做到。最后处理区间加。这个一样可以用差分来做，那么最后的复杂度为 。

• 差分，我们定义数组 ，如果原值为 。那么满足 。那么给 全部 等同于 。这样我们对于区间加就可以直接修改两个点来操作了。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
const int N = 1e5 + 100,inf = 0x3f3f3f3f,mod = 1e9 + 7;
int A[N],L[N],R[N],C[N],ans[N],n,m;
void del(int &x,int y) {x -= y;if(x<0)x+=mod;}
void upd(int &x,int y) {x += y;if(x>=mod)x-=mod;}
int main() {
    n = read();m = read();
    for(int i = 1;i <= m;i++) A[i] = read(),L[i] = read(),R[i] = read();
    for(int i = m;i >= 1;i--) {
        upd(C[i],C[i+1]);
        if(A[i] == 2) del(C[L[i] - 1],C[i] + 1),upd(C[R[i]],C[i] + 1);
        if(A[i] == 1) del(ans[R[i] + 1],C[i] + 1),upd(ans[L[i]],C[i] + 1);
    }
    int now = 0;
    for(int i = 1;i <= n;i++) {
        upd(now,ans[i]);
        printf("%d ",now);
    }
    printf("\n");
    return 0;
}