分析

我们看出，这是一个匹配问题。左边的点只能匹配右边的节点。而一个节点可以匹配的数量为 。我们可以考虑用网络流来解决这个问题。

• 向左边节点 连接一条容量为 边。

• 右边节点 向 连接一条容量为 的边。

• 如果右侧节点 满足 ，那么左侧节点 向 连一条容量为 的边。最后 。

但是我们发现这样连边时间复杂度为 的，要考虑优化。因为连的边是一个连续的区间，我们其实可以考虑线段树优化建边。那么总边数为 。 那么用 的总复杂度为 。由于网络流好像基本跑不满，所以也就过了。

代码

#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 = 4e6 + 10,inf = 0x3f3f3f3f;
struct Line{int l,r,v;}line[N];
struct Edge{int to,nxt,cap;}e[N];
int n,m,dis[N],head[N],cur[N],ecnt;
queue<int> Q;
void add(int x,int y,int cap) {
    e[++ecnt].to = y;e[ecnt].cap = cap;e[ecnt].nxt = head[x];head[x] = ecnt;
    e[++ecnt].to = x;e[ecnt].cap = 0;  e[ecnt].nxt = head[y];head[y] = ecnt;
}
void update(int u,int l,int r,int id) {
    if(line[id].l <= l && r <= line[id].r) {add(id + 4 * n,u,inf);return;}
    if(l > line[id].r || r < line[id].l) return;
    int mid = l + r >> 1;
    update(u<<1,l,mid,id);update(u<<1|1,mid+1,r,id);
}
void build(int u,int l,int r) {
    if(l == r) {add(u,4 * n + m + 1,1);return;}
    int mid = l + r >> 1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    add(u,u<<1,inf);add(u,u<<1|1,inf);
}
bool bfs(int s,int t) {
    while(!Q.empty()) Q.pop();memset(dis,0,sizeof(dis));dis[s] = 1;
    Q.push(s);while(!Q.empty()) {
        int x = Q.front();Q.pop();for(int i = head[x];i;i = e[i].nxt) {
            if(!dis[e[i].to] && e[i].cap > 0) {
                dis[e[i].to] = dis[x] + 1;Q.push(e[i].to);
                if(e[i].to == t) return true;
            }
        }
    }
    return false;
}
int dfs(int x,int a,int t) {
    if(t == x || a == 0) return a;
    int flow = 0,f;for(int i = cur[x];i;i = e[i].nxt) {
        cur[x] = i;int y = e[i].to;
        if((dis[y] == dis[x] + 1) && ((f=dfs(y,min(a,e[i].cap),t))>0)) {
            e[i].cap -= f;e[i^1].cap += f;flow += f;a -= f;if(!a) break;
        }
    }
    return flow;
}
int main() {
    while(scanf("%d%d",&n,&m) != -1) {
        ecnt = 1;memset(head,0,sizeof(head));
        for(int i = 1;i <= m;i++) {
            scanf("%d%d%d",&line[i].l,&line[i].r,&line[i].v);update(1,1,n,i);
        }
        build(1,1,n);
        int S = 0,T = 4 * n + m + 1,maxflow = 0;
        for(int i = 1;i <= m;i++) add(S,4 * n + i,line[i].v);
        while(bfs(S,T)) {
            for(int i = 0;i <= T;i++) cur[i] = head[i];
            maxflow += dfs(S,inf,T);
        }
        printf("%d\n",maxflow);
    }

    return 0;
}