线段树优化建图2模板（暂无正确性保证）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int mod=1e9+7;
int cnt;
int id1[18*N],id2[18*N];
struct node{
    int l,r;
    int id;
}in[N<<2],out[N<<2];
vector<int> g[N*10];
int st[N*10],n,m,d[N*10];
void add(int u,int v){
    g[u].push_back(v);
    st[v]++;
}
int build(int k,int l,int r,node tr[],int *a,int type){
    tr[k]={l,r,++cnt};
    if(l==r){
        a[l]=cnt;
        return tr[k].id;
    }
    int mid=l+r>>1;
    if(type){
        add(tr[k].id,build(k<<1,l,mid,tr,a,type));
        add(tr[k].id,build(k<<1|1,mid+1,r,tr,a,type));
    }
    else{
        add(build(k<<1,l,mid,tr,a,type),tr[k].id);
        add(build(k<<1|1,mid+1,r,tr,a,type),tr[k].id);
    }
    return tr[k].id;
}
void modify(int u,int l,int r,int now,node tr[],int type){
    if(tr[u].l>=l&&tr[u].r<=r){
        if(type)
            add(now,tr[u].id);
        else
            add(tr[u].id,now);
        return ;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)
        modify(u<<1,l,r,now,tr,type);
    if(r>mid)
        modify(u<<1|1,l,r,now,tr,type);
}
int f[N*10];
queue<int> q;
ll l[N];
struct que{
    int id,l,r;
}qq[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int i;
    build(1,1,m,in,id1,0);
    int sign=cnt+1;
    build(1,1,m,out,id2,1);
    for(i=1;i<=m;i++){
        int opt,l,r;
        cin>>opt>>l>>r;
        qq[i]={opt,l,r};
        if(opt==1){
            f[id2[i]]++;
        }
        else{
            f[id1[i]]=1;
            modify(1,l,r,id1[i],out,1);
        }
    }
    for(i=1;i<=m;i++){
        if(qq[i].id==2)
        if(!st[id1[i]]){
            q.push(id1[i]);
        }
    }
    if(!st[sign]){
        q.push(sign);
    }
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=0;i<g[t].size();i++){
            int j=g[t][i];
            st[j]--;
            f[j]=(f[j]+f[t])%mod;
            if(!st[j])
                q.push(j);
        }
    }
    for(i=1;i<=m;i++){
        if(qq[i].id==1){
            l[qq[i].l]+=f[id2[i]];
            l[qq[i].r+1]-=f[id2[i]];
        }
    }
    for(i=1;i<=n;i++){
        l[i]+=l[i-1];
    }
    for(i=1;i<=n;i++)
        cout<<l[i]<<" ";
    cout<<endl;
}