网络优化

话说我不是首杀好难过

但是这样连边,复杂度是的

#include <bits/stdc++.h>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
const int maxn=6e6+10;
const int inf=1e9;
int n,m,s,t,dis[maxn],id;
struct edge{
    int to,nxt,flow;
}d[maxn]; int head[maxn],cnt=1;
int l[maxn],r[maxn],v[maxn];
void add(int u,int v,int flow){
    d[++cnt]=(edge){v,head[u],flow},head[u]=cnt;
    d[++cnt]=(edge){u,head[v],0},head[v]=cnt;
}
bool bfs()
{
    for(int i=s;i<=t;i++)    dis[i]=0;
    dis[s]=1;
    queue<int>q; q.push( s );
    while( !q.empty() )
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=d[i].nxt )
        {
            int v=d[i].to;
            if( d[i].flow&&dis[v]==0 )
            {
                dis[v]=dis[u]+1;
                if( v==t )    return true;
                q.push( v );
            }
        }
    }
    return false;
}
int dinic(int u,int flow)
{
    if( u==t )    return flow;
    int res=flow;
    for(int i=head[u];i&&res;i=d[i].nxt )
    {
        int v=d[i].to;
        if( dis[v]==dis[u]+1&&d[i].flow)
        {
            int temp=dinic(v,min(res,d[i].flow) );
            if( temp==0 )    dis[v]=0;
            res-=temp;
            d[i].flow-=temp;
            d[i^1].flow+=temp;
        }
    }
    return flow-res;
}
void build(int rt,int l,int r)
{
    id = max( id,n+m+rt );
    if( l==r ){ add(rt+m+n,l+m,inf); return; }
    build(lson); build(rson);
    add(rt+m+n,ls+m+n,inf);
    add(rt+m+n,rs+m+n,inf);
}
void run(int rt,int l,int r,int u,int L,int R)
{
    if( r<L||l>R )    return;
    if( L<=l&&R>=r )
    {
        add(u,rt+n+m,inf);
        return;
    }
    run(lson,u,L,R); run(rson,u,L,R);
}
signed main()
{
    while( cin >> n >> m )
    {
        s=0,id=0;
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&l[i],&r[i],&v[i] );
            run(1,1,n,i,l[i],r[i] );
            add(s,i,v[i] );
        }
        t = id+1;
        for(int i=1;i<=n;i++)    add(i+m,t,1);
        int ans=0;
        while( bfs())    ans+=dinic(s,inf);
        cout << ans << '\n';
        cnt = 1;
        for(int i=s;i<=t;i++)    head[i]=0;
    }
}