竟然在BZOJ上拿了Rank1太给力啦。 p.s.:汗，一发这个就被一堆人在2月27号强势打脸……

传送门(BZOJ)

传送门(UOJ)

说说这道题目吧：

首先是说说这个构图吧。因为有选择关系，我们很容易想到最小割。

Ans = sigma(i为白色){w[i]} + sigma(i为黑色){b[i]} - sigma(奇怪的i){p[i]}

转化一下就变成了sigma(所有的i){w[i]+b[i]} - sigma(i为白色){b[i]} -sigma(i为黑色){w[i]} - sigma(奇怪的i){p[i]}

对于每个店S向i连一条容量为b[i]的点(如果满流意味着选择白色)， i向T连一条容量为w[i]的点(如果满流意味着选择黑色)

若点i会变得奇怪，我们新建一个点i'来，连一条容量为p[i]的边，表示i变得奇怪，对于范围内的点j，从i'连一条容量为INF的边

然后我们发现边数是O(N^2)的，跑即使是跑网络流这种O(玄学)的算法也不能过的。

所以是不是就没法做了呢？VFK大毒瘤？

其实VFK给我们带来了一片新天地，太神啦，我们可以把边直接连在区间上！！！

考虑用线段树，最底层的节点(表示区间长度为1的)连边向对应的节点，每一层的父亲连向儿子，那么就可以把变数变成O(nlgn)个

就可以跑网络流啦

但是VFK是好（du）人（liu），给我们来了一个只能向编号小的连边，那么就强行可持久化了。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#define MAXN 5005

#define MAXM 1000005

#define INF 999999999

using namespace std;

struct { int v, nxt, f; } e[MAXM];

int Adj[MAXN * 20], c = -1, n, m, S, T, a[MAXN], b[MAXN], w[MAXN], vd[MAXN * 20];

int L[MAXN], R[MAXN], P[MAXN], Q[MAXN*3], N, Ans, tot, sz, rt[MAXN], d[MAXN * 20], vn;

inline void Add(int u, int v, int f) {

    ++ c; e[c].v = v; e[c].f = f; e[c].nxt = Adj[u]; Adj[u] = c;

    ++ c; e[c].v = u; e[c].f = 0; e[c].nxt = Adj[v]; Adj[v] = c;

}

struct Seg { int lc, rc; } t[MAXN * 20];

inline void GET(int &n) {

    static char c; n = 0;

    do c = getchar(); while('0' > c || c > '9');

    do n=n*10+c-'0', c=getchar(); while('0' <= c && c <= '9');

}

inline int Binary_Search(int p) {

    int l = 1, r = N, mid, ans = 0;

    while(l <= r) {

        mid = (l + r) >> 1;

        if(Q[mid] >= p) { ans = mid; r=mid-1; }

        else l = mid+1;

    }

    return ans;

}

void Link(int rt, int l, int r, int i) {

    if(L[i] > r || l > R[i]) return;

    if(L[i] <= l && r <= R[i]) { Add(n+i, tot+rt, INF); return; }

    int mid = (l + r) >> 1;

    if(t[rt].lc) Link(t[rt].lc, l, mid, i);

    if(t[rt].rc) Link(t[rt].rc, mid+1,r,i);

}

void Insert(int &rt, int p, int l, int r, int i) {

    rt = ++ sz;

    if(l == r) {

        Add(tot + rt, i, INF);

        if(p) Add(tot + rt, tot + p, INF);

        return;

    }

    int mid = (l + r) >> 1;

    if(a[i] <= mid) t[rt].rc = t[p].rc, Insert(t[rt].lc, t[p].lc, l, mid, i);

    else t[rt].lc = t[p].lc, Insert(t[rt].rc, t[p].rc, mid+1, r, i);

    if(t[rt].lc) Add(tot+rt, tot+t[rt].lc, INF);

    if(t[rt].rc) Add(tot+rt, tot+t[rt].rc, INF);

}

int Aug(int u, int augco) {

    if(u == T) return augco;

    int delta, dmin = tot - 1, augc = augco, v;

    for(int i = Adj[u]; ~i; i = e[i].nxt) if(e[i].f) {

        v = e[i].v;

        if(d[v] + 1 == d[u]) {

            delta = Aug(v, min(augc, e[i].f));

            e[i].f -= delta; e[i^1].f += delta;

            augc -= delta;

            if(d[S] >= tot || !augc) return augco - augc;

        }

        if(dmin > d[v]) dmin = d[v];

    }

    if(augco == augc) {

        -- vd[d[u]];

        if(!vd[d[u]]) d[S] = tot;

        ++ vd[d[u] = dmin + 1];

    }

    return augco - augc;

}

int sap() {

    vd[S] = tot; int ans = 0;

    while(d[S] < tot)

        ans += Aug(S, INF);

    return ans;

}

int main() {

    GET(n); memset(Adj, -1, sizeof Adj);

    for(int i = 1; i <= n; ++ i) {

        GET(a[i]); GET(b[i]); GET(w[i]);

        GET(L[i]); GET(R[i]); GET(P[i]);

        Q[++ N] = a[i]; Q[++N] = L[i]; Q[++N] = R[i];

        Ans += b[i] + w[i];

    }

    sort(Q+1, Q+N+1); N = unique(Q+1, Q+N+1) - (Q+1);

    S = 2*n + 1; T = S+1;

    tot = T;

    for(int i = 1; i <= n; ++ i) {

        a[i] = Binary_Search(a[i]);

        L[i] = Binary_Search(L[i]);

        R[i] = Binary_Search(R[i]);

        Add(S, i, b[i]); Add(i, T, w[i]); Add(i, i+n, P[i]);

    }

    for(int i = 1; i <= n; ++ i) {

        if(i > 1) Link(rt[i-1], 1, N, i);

        Insert(rt[i], rt[i-1], 1, N, i);

    }

    tot = tot + sz; vn = tot;

    printf("%d\n", Ans - sap());

    return 0;

}