筱玛爱线段树

操作二可真是太毒瘤了...可以一直嵌套嵌套嵌套

能不能对操作二进行差分呢??当然可以

而且有一个很重要的性质,前面的操作二不会影响后面的操作二

所以从后往前看所有操作二,对操作在树状数组上差分

为什么在树状数组上?因为可以直接查询此时操作需要执行几次

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10; 
const int mod=1e9+7;
int l[maxn],r[maxn],top,type[maxn];
int zhi[maxn],a[maxn],n,m,ok[maxn];
int lowbit( int x ){ return x&(-x); }
int ask(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x))    ans = ( ans+ok[x] )%mod;
    return ans; 
}
void add(int x,int k)
{
    for(;x<=m;x+=lowbit(x))    ok[x] = ( ok[x]+k )%mod;    
}
signed main()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
        scanf("%lld%lld%lld",&type[i],&l[i],&r[i]);
    for(int i=m;i>=1;i--)
        if( type[i] == 2 )
        {
            int x=ask( i );
            add(l[i],x+1); add(r[i]+1,-x-1);
        }
    for(int i=1;i<=m;i++)    a[i]=ask(i);
    for(int i=1;i<=m;i++)
        if( type[i] ==1 )
        {
            zhi[l[i]]+=a[i]+1;    a[l[i]]%=mod;
            zhi[r[i]+1]-=a[i]+1;    a[r[i]+1]%=mod;
        }    
    for(int i=1;i<=n;i++)
        zhi[i] = ( zhi[i]+zhi[i-1] )%mod;
    for(int i=1;i<=n;i++)    cout << (zhi[i] % mod + mod) % mod << " "; 
}