线段树优化建图+最大流

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
#define mem(s, v) memset(s, v, sizeof s)
#define FILEIN(s) freopen(s".in", "r", stdin)
#define FILEOUT(s) freopen(s".out", "w", stdout)

inline int read(void) {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return f * x;
}

const int maxk = 100005, maxm = 20005, inf = 1e8;
const int maxv = maxk * 4 + maxm, maxe = maxk * 1 + maxk * 4 + maxm * 18 * 2;

int n, m, K;

int head[maxv], tot = 1, sz;
int rt[2], S, T;
int son[maxk << 2][2], L[maxk << 2], R[maxk << 2];

int cur[maxv], d[maxv];

int pos[2][maxk];

struct Edge {
    int y, next, w;
    Edge() {}
    Edge(int _y, int _next, int _w) : y(_y), next(_next), w(_w) {}
}e[maxe << 1];

inline void connect(int x, int y, int w) {
    e[++tot] = Edge(y, head[x], w);
    head[x] = tot;
}

inline void add(int x, int y, int w) {
    connect(x, y, w); connect(y, x, 0);
}

inline int New() { ++sz; return sz; }

void build(int o, int l, int r, bool k) {
    L[o] = l; R[o] = r;
    if (l == r) {
        pos[k][l] = o;
        return;
    }
    son[o][0] = New(); son[o][1] = New();
    int mid = (l + r) >> 1;
    build(son[o][0], l, mid, k);
    build(son[o][1], mid + 1, r, k);

    if (!k) add(son[o][0], o, inf), add(son[o][1], o, inf);
    else add(o, son[o][0], inf), add(o, son[o][1], inf);
}

void link(int o, int ql, int qr, int t, int l, bool k) {
    if (ql <= L[o] && R[o] <= qr) {
        if (!k) add(o, t, l);
        else add(t, o, l);
        return;
    }
    int mid = (L[o] + R[o]) >> 1;
    if (ql <= mid) link(son[o][0], ql, qr, t, l, k);
    if (qr > mid) link(son[o][1], ql, qr, t, l, k);
}

bool bfs(void) {
    queue<int>q;
    cur[S] = head[S];
    q.push(S);
    mem(d, -1); d[S] = 1;
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = e[i].next) {
            int y = e[i].y;
            if (e[i].w && d[y] == -1) {
                d[y] = d[x] + 1;
                cur[y] = head[y];
                if (y == T) return true;
                q.push(y);
            }
        }
    }
    return false;
}

int find(int x, int limit) {
    if (x == T) return limit;
    int flow = 0;
    for (int i = cur[x]; i && flow < limit; i = e[i].next) {
        cur[x] = i;
        int y = e[i].y;
        if (e[i].w && d[y] == d[x] + 1) {
            int t = find(y, min(e[i].w, limit - flow));
            if (!t) d[y] = -1;
            flow += t;
            e[i].w -= t;
            e[i ^ 1].w += t;
        }
    }
    return flow;
}

inline void dinic(void) {
    int r = 0, flow;
    while (bfs()) while (flow = find(S, inf)) r += flow;
    printf("%d\n", min(r, n));
}

int main() {
    n = read(); m = read(); K = read();
    rt[0] = New();
    build(rt[0], 1, K, 0);

    rt[1] = New();
    build(rt[1], 1, K, 1);

    for (int i = 1; i <= K; ++i) //add(pos[1][i], pos[0][i], inf);
        connect(pos[0][i], pos[1][i], inf),
        connect(pos[1][i], pos[0][i], inf);

    S = New(); T = New();
    add(S, pos[0][1], inf); add(pos[1][K], T, inf);

    while (m--) {
        int opt = read(), limit = read();
        if (opt == 1) {
            int a = read(), b = read();
            add(pos[0][a], pos[1][b], limit);
        }
        else if (opt == 2) {
            int l = read(), r = read(), b = read();
            link(rt[0], l, r, pos[1][b], limit, 0);
        }
        else if (opt == 3) {
            int a = read(), l = read(), r = read();
            link(rt[1], l, r, a, limit, 1);
        }
        else if (opt == 4) {
            int l1 = read(), r1 = read(), l2 = read(), r2 = read(), x = New();
            link(rt[0], l1, r1, x, limit, 0);
            link(rt[1], l2, r2, x, limit, 1);
        }
    }

    dinic();
    return 0;
}

出题人您能提供一下倒数第二个点的数据吗？

@Wen_kr