G. Oleg and chess

先考虑网络流。。。是最朴素的二分图匹配。。。
还是设法要减少边的规模。。。我们类比扫描线来做矩形合并。。
从左到右扫描每一列，我们用函数式线段树，就能维护出代表这一列的线段树的根节点状态。。
那么只要从源点向根节点连过去一条容量为 1 的边即可。。注意需要保证这些线段树共享同一组闭合状态。。。

总感觉有更好的做法。。。

const int N = int(1e4) + 9;

int T[N], H[N]; VI adj[N];
int n, m;

namespace Chairman_Tree {
#define lx c[0][x]
#define rx c[1][x]
#define ly c[0][y]
#define ry c[1][y]
#define lz c[0][z]
#define rz c[1][z]
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
    const int NN = 100*N;
    int c[2][NN]; int tot;
    int pp; int dd;
    int new_node() {
        return ++tot;
    }
    int new_node(int y) {
        int x = ++tot; lx = ly; rx = ry;
        return x;
    }

    void Build(int& x, int l, int r) {
        if (l == r) {
            x = l;
        } else {
            x = new_node();
            Build(lc);
            Build(rc);
        }
    }

    int Insert(int x, int l, int r, int y, int a, int b) {
        if (b < l || r < a) return x;
        if (a <= l && r <= b) {
            return y;
        } else {
            x = new_node(x);
            lx = Insert(lc, ly, a, b);
            rx = Insert(rc, ry, a, b);
            return x;
        }
    }

} using namespace Chairman_Tree;

VII del[N], add[N];

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(n); Rush {
        int x1, y1, x2, y2; RD(x1, y1, x2, y2); ++x2;
        add[x1].PB({y1, y2});
        del[x2].PB({y1, y2});
    }

    atcoder::mf_graph<int> G(NN);
    int s = 0, t = n+1; REP_1(i, n) G.add_edge(i, t, 1);
    tot = t;

    int x; Build(x, 1, n); int o = x, a = 0; REP_1(i, n) {
        int y = x;
        for (auto e: del[i]) x = Insert(x, 1, n, o, e.fi, e.se);
        for (auto e: add[i]) x = Insert(x, 1, n, 0, e.fi, e.se);
        if (x != y) {
            if (y && a) G.add_edge(s, y, a);
            a = 0;
        }
        ++a;
    }
    if (x) G.add_edge(s, x, a);

    FOR_1(x, t+1, tot) {
        if (lx) G.add_edge(x, lx, INF);
        if (rx) G.add_edge(x, rx, INF);
    }

    cout << G.flow(s, t) << endl;
}

Posted by xiaodao
Category: 日常