G_solution.cpp

void solve(istream& in, ostream& out) {
    int n = next<int>(in);
    Graph g;
    Graph::Node s = g.addNode(), t = g.addNode();
    auto cap = g.arcMap<int>();
    vector<vector<Graph::Node>> levelsIn, levelsOut;
    levelsIn.push_back(g.addNodes(n));
    levelsOut.push_back(g.addNodes(n));
    forn (int, i, n) {
        g.addEdge(s, levelsIn[0][i]).withUV(cap, 1);
        g.addEdge(levelsOut[0][i], t).withUV(cap, 1);
    }
    for (int l = 1; (1 << l) <= n; ++l) {
        levelsIn.push_back(g.addNodes(n - (1 << l) + 1));
        levelsOut.push_back(g.addNodes(n - (1 << l) + 1));
        forn (int, i, n - (1 << l) + 1) {
            g.addEdge(levelsIn[l - 1][i], levelsIn[l][i]).withUV(cap, n);
            g.addEdge(levelsIn[l - 1][i + (1 << (l - 1))], levelsIn[l][i]).withUV(cap, n);
            g.addEdge(levelsOut[l][i], levelsOut[l - 1][i]).withUV(cap, n);
            g.addEdge(levelsOut[l][i], levelsOut[l - 1][i + (1 << (l - 1))]).withUV(cap, n);
        }
    }
    int qs = next<int>(in);
    using evt = tuple<int, int, pair<int, int>>;
    vector<evt> evs;
    forn (int, q, qs) {
        int x1 = next<int>(in) - 1;
        int y1 = next<int>(in) - 1;
        int x2 = next<int>(in) - 1;
        int y2 = next<int>(in) - 1;
        evs.push_back(evt{x1, +1, {y1, y2 + 1}});
        evs.push_back(evt{x2 + 1, -1, {y1, y2 + 1}});
    }
    evs.push_back(evt{0, -1, {0, n}});
    evs.push_back(evt{n, +1, {0, n}});
    sort(all(evs));
    auto insertRect = [&](int x0, int x1, int y0, int y1) {
        if (x0 == x1 || y0 == y1) {
            return;
        }
        int dx = 0, dy = 0;
        while (x0 + (1 << (dx + 1)) <= x1) {
            ++dx;
        }
        while (y0 + (1 << (dy + 1)) <= y1) {
            ++dy;
        }
        auto u = g.addNode();
        g.addEdge(levelsIn[dx][x0], u).withUV(cap, n);
        g.addEdge(levelsIn[dx][x1 - (1 << dx)], u).withUV(cap, n);
        g.addEdge(u, levelsOut[dy][y0]).withUV(cap, n);
        g.addEdge(u, levelsOut[dy][y1 - (1 << dy)]).withUV(cap, n);
        dbg(x0 + 1, y0 + 1, x1, y1, u.id);
    };
    map<int, pair<int, int>> ranges;
    for (auto& e : evs) {
        int x = get<0>(e);
        auto& range = get<2>(e);
        if (get<1>(e) == -1) {
            ranges[range.first] = {range.second, x};
        } else {
            auto it = ranges.upper_bound(range.first);
            --it;
            pair<int, int> outer;
            outer.first = it->first;
            while (it != ranges.end() && it->first < range.second) {
                insertRect(it->second.second, x, it->first, it->second.first);
                outer.second = it->second.first;
                auto jt = it;
                it++;
                ranges.erase(jt);
            }
            if (outer.first < range.first) {
                ranges[outer.first] = {range.first, x};
            }
            if (range.second < outer.second) {
                ranges[range.second] = {outer.second, x};
            }
        }
    }
    PushRelabel<int> f(g, cap);
    out << f.run(s, t) << "\n";
}