首先还是类似 POJ 3469. Dual Core CPU 的最小割建模。
难点是对每个节点 i，我们需要构造辅助节点 i’，满足，如果存在满足条件的 j 在 T 割，那么 i’ 也一定在 T 割。

因为找 j 的过程是一个区间关系，暴力构造 i’ 的话边数太多。
类比确定染色方案后，查询结果这个问题，这个显然可以离散化 + 线段树（树状数组），
我们发现可以使用线段树来刻画这些辅助节点以减少边的规模。（类似边分治里的加辅助结点？）
（3b1b 演示的话。。大概就是把 i’ 这个辅助点，慢慢扩散成一个线段树，每扩散一层，叶子所连的边的规模就少一层。。）。

这种题目的出法后来在网赛里也出过。。。
另外这个题要考虑 j <= i 这个限制，最后还需要使用函数式线段树。

const int N = int(5e3) + 9;

int T[N], X[N], Y[N]; vector<int> A;
int n, z;

namespace ST{

#define lx l[x]
#define rx r[x]
#define ly l[y]
#define ry r[y]
#define ml (ll + rr >> 1)
#define mr (ml + 1)

    const int NN = N*18 + 9;
    int l[NN], r[NN], tot;

    int new_node(){
        return ++tot;
    }

    int Add(int y, int p, int i){
        int x = new_node(), root = x; int ll = 0, rr = n-1;

        while (ll < rr){
            if (p < mr){
                lx = new_node(), rx = ry;
                x = lx, y = ly, rr = ml;
            }
            else {
                lx = ly, rx = new_node();
                x = rx, y = ry, ll = mr;
            }
        }

        X[i] = x; Y[i] = y;
        return root;
    }

    void Query(int x, int ll, int rr, int a, int b, VI& L) {
        if (!x || b < ll || rr < a) return;
        if (a <= ll && rr <= b) {
            L.PB(x);
        } else {
            Query(lx, ll, ml, a, b, L);
            Query(rx, mr, rr, a, b, L);
        }
    }
} using namespace ST;

struct cell{
    int a,b,w,l,r,p;
    void in() {
        RD(a,b,w,l,r,p); A.PB(a);
        z += b; z += w;
    }
} C[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); REP(i, n) C[i].in();

    UNQ(A); REP(i, n) {
        C[i].l = LBD(A, C[i].l); C[i].r = UBD(A, C[i].r)-1;
        T[i] = ST::Add(i ? T[i-1] : 0, C[i].a = LBD(A, C[i].a), i);
    }

    atcoder::mf_graph<int> G(n+n+2+ST::tot);
    int s = 2*n, t = n+n+1;

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

    REP(i, n) {
        G.add_edge(s, i, C[i].b);
        G.add_edge(i, t, C[i].w);
        G.add_edge(i, n+i, C[i].p);
        /*REP(j, i) if (C[i].l <= C[j].a && C[j].a <= C[i].r) {
            G.add_edge(i+n, j, INF);
        }*/
        G.add_edge(t+X[i], i, INF); if (Y[i]) G.add_edge(t+X[i], t+Y[i], INF);
        VI L; ST::Query(T[i], 0, n-1, C[i].l, C[i].r, L);
        for (auto l: L) G.add_edge(n+i, t+l, INF);
    }

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

Posted by xiaodao
Category: 日常