- BZOJ 传送门 | UOJ 传送门
- https://blog.bill.moe/bzoj3218-a-b/ 这个题解里有很棒的图，看一眼就会做了。
- https://ctz45562.github.io/2019/04/28/bzoj-3218-a+b-Problem/ 如果你还不会，这个题解里有仔细讲解割和解的对应关系。

…

const int N = int(1e5) + 9; int a[N], l[N], r[N]; VI I; int n, z; struct Dinitz { const static int M = N*20; int D[N], hd[N], suc[M], to[M], cap[M]; int n, m, s, t; inline void ae(int x, int y, int c){ suc[m] = hd[x], hd[x] = m, to[m] = y, cap[m++] = c, suc[m] = hd[y], hd[y] = m, to[m] = x, cap[m++] = 0; } #define v to[i] #define c cap[i] #define f cap[i^1] bool bfs(){ static int Q[N]; int cz = 0, op = 1; fill(D, D+n, 0); D[Q[0] = s] = 1; while (cz < op){ int u = Q[cz++]; REP_G(i, u) if (!D[v]&&c){ D[Q[op++]=v] = D[u]+1; if (v==t) return 1; } } return 0; } LL run(){ LL z=0; while (bfs()){ static int cur[N], pre[N]; int u=s;pre[s]=-1;cur[s]=hd[s];while (~u){ #define i cur[u] if (u==t){ int d=INF;for(u=s;u!=t;u=v)checkMin(d,c); z+=d;for(u=s;u!=t;u=v)f+=d,c-=d;u=s; } #undef i int i;for(i=cur[u];i;i=suc[i])if(D[u]+1==D[v]&&c){cur[u]=i,cur[v]=hd[v],pre[v]=u,u=v;break;} if (!i)D[u]=0,u=pre[u]; } } return z; } #undef f #undef c #undef v void init() { RD(n); m=2,s=2*n+1,t=2*n+2; REP_1(i, n) { I.PB(RD(a[i])); int b, w; RD(b, w); z += b+w; I.PB(RD(l[i])); I.PB(RD(r[i])); ae(s,i,b); ae(i,t,w); ae(i,n+i,RD()); } UNQ(I); REP_1(i, n) { a[i]=LBD(I,a[i])+1; l[i]=LBD(I,l[i])+1; r[i]=LBD(I,r[i])+1; } ::n = n; n = t+1; } } G; struct Presitent_Segment_Tree { const static int N = ::N * 10; #define lx l[x] #define rx r[x] #define ml (ll + rr >> 1) #define mr (ml + 1) int l[N], r[N], nn; int n, s, t, a, b; void add_edge(int x, int y) { G.ae(G.t+x, G.t+y, INF); } inline int new_node(int y) { int x = ++nn; G.n += 1; if (y) { lx = l[y]; rx = r[y]; add_edge(x, y); } return x; } int add(int y, int p, int t) { int x = new_node(y), root = x, ll = 1, rr = n; while (ll < rr) { if (p < mr) { add_edge(x, lx = new_node(lx)); x = lx; rr = ml; } else { add_edge(x, rx = new_node(rx)); x = rx; ll = mr; } } add_edge(x, t); return root; } void gao(int x,int ll,int rr) { if (!x || b < ll || rr < a) return; if (a <= ll && rr <= b) { add_edge(s, x); return; } gao(lx,ll,ml); gao(rx,mr,rr); } void gao(int x, int a, int b, int s) { this->a = a; this->b = b; this->s = s; gao(x, 1, n); } } T; int root[N]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif G.init(); T.n = SZ(I); REP_1(i, n) { T.gao(root[i-1],l[i],r[i],n+i-G.t); root[i]=T.add(root[i-1],a[i],i-G.t); } printf("%d\n", z - G.run()); }