Original link: https://www.shuizilong.com/house/archives/uoj-77-ab-problem/
The first is the minimum cut modeling similar to POJ 3469. Dual Core CPU .
The difficulty is that for each node i, we need to construct an auxiliary node i’, which is satisfied. If there is a j cut at T that satisfies the condition, then i’ must also be cut at T.
Because the process of finding j is an interval relationship, there are too many edges if i’ is constructed violently.
After the coloring scheme is determined by analogy, the question of query results can obviously be discretized + line segment tree (tree array),
We found that we could use a segment tree to characterize these auxiliary nodes to reduce the size of the edges. (Similar to adding auxiliary nodes in edge divide and conquer?)
(In the case of 3b1b’s demonstration… it is probably to spread the auxiliary point i’ into a line segment tree slowly. Each time it spreads, the scale of the edge connected to the leaves is reduced by one level…).
The method of this kind of question was also appeared in the online competition later. . .
In addition, this question needs to consider the limitation of j <= i, and finally needs to use a functional segment tree.
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; }
This article is reprinted from: https://www.shuizilong.com/house/archives/uoj-77-ab-problem/
This site is for inclusion only, and the copyright belongs to the original author.