n个方格从左到右排成一列, 给它们黑白染色. 如果方格i染成黑色, 获得bi收益; 染成白色, 获得wi收益. 如果一个黑色方格i的左边存在白色方格j, 使得li≤aj≤ri, 则称i为奇怪的方格, 收益减少pi. 求所有染色方案中最大的收益. (n≤5000, a,l,r≤10^9, b,w≤2*10^5, p≤3*10^5, 每个测试点时限2s, 内存限制48MB) 事先知道这题是最小割, 用主席树优化建图......
尝试暴力建图.
我是转化成最大权闭合图做的......因为有[bzoj 4873] [Shoi2017]寿司餐厅的经验: a或b发生将导致c, 但是它们同时发生并不会使c的影响扩大.
不妨先把所有格子染成白色, 令选中的格子染成黑色. 把存在量词转化为全称量词: 先将bi-=pi, 如果黑色格子i左边所有满足li≤aj≤ri的格子j都是黑色, 获得pi的好看度. 如果选择得到这pi的收益, 某些格子必须选上; 如果这些格子选上了, 由于我们求的是最大权闭合图, 自然也会获得这pi的收益.
在CF上见过几道类似的题. 从一个点向一个区间连边, 可以建线段树. 这里同时限制了位置区间和值域, 所以采用可持久化权值线段树.
WA了一发, 因为叶子节点得向外面连边, 而我在可持久化线段树上插入时, 覆盖掉了之前的信息. 其实解决方法很简单, 新建叶子的时候在网络里连一条新叶子到旧叶子的边即可. 就像 += 操作.
题解上看到神犇们都是直接用最小割建图的......
首先, 本题需要最大化收益, 所以我们从 Σbi+Σwi 中减去多算的.
还是先考虑暴力建图. 如果i和S连通, 则染成黑色; 如果i和T连通, 则染成白色. 如果每一对(j,i)都会获得-pi的收益, 这样建图就可以: 
然而(j1,i),(j2,i)均存在也只会获得-pi的收益. 加个虚拟节点i'即可解决: 
const int N = 5001, MAXV = N*16 + 2, MAXE = 225000, inf = 2e9;
struct MaximumFlow
{
struct Edge {
int to, c, nxt;
} E[MAXE*2 + 2];
int s, t, n, Q[MAXV], adj[MAXV], lv[MAXV], cur[MAXV];
void add(int u, int v, int f)
{
static int ptr = 2;
E[ptr] = (Edge){v, f, adj[u]};
adj[u] = ptr++;
E[ptr] = (Edge){u, 0, adj[v]};
adj[v] = ptr++;
}
bool bfs()
{
memset(lv, -1, sizeof(int)*n);
int front = 0, rear = 1;
Q[0] = s;
lv[s] = 0;
while (front < rear)
{
int u = Q[front++];
for (int i = adj[u]; i; i = E[i].nxt)
{
int v = E[i].to;
if (E[i].c && lv[v] == -1)
{
lv[v] = lv[u] + 1;
Q[rear++] = v;
}
}
}
return lv[t] != -1;
}
int dfs(int u, int f)
{
if (u == t) return f;
int r = f;
for (int& i = cur[u]; i; i = E[i].nxt)
{
int v = E[i].to;
if (lv[v] == lv[u] + 1 && E[i].c)
{
int t = dfs(v, min(r, E[i].c));
E[i].c -= t;
E[i^1].c += t;
r -= t;
if (!r) break;
}
}
return f-r;
}
int solve(int _s, int _t, int _n)
{
s = _s, t = _t, n = _n;
int f = 0;
while (bfs())
{
rep (i, 0, n) cur[i] = adj[i];
f += dfs(s, inf);
}
return f;
}
} solver;
inline void add(int u, int v, int f)
{
solver.add(u, v, f);
}
int offset;
struct Seg
{
int ptr, rt[N], lc[14*N], rc[14*N];
void insert(int& o, int p, int a, int i, int l, int r)
{
o = ++ptr;
if (l == r)
{
add(o + offset, i, inf);
if (p) add(o + offset, p + offset, inf);
return;
}
int m = (l+r)/2;
if (a <= m) insert(lc[o], lc[p], a, i, l, m), rc[o] = rc[p];
else insert(rc[o], rc[p], a, i, m+1, r), lc[o] = lc[p];
if (lc[o])
add(o + offset, lc[o] + offset, inf);
if (rc[o])
add(o + offset, rc[o] + offset, inf);
}
void query(int o, int L, int R, int i, int l, int r)
{
if (!o) return;
if (L <= l && r <= R) return add(i, o + offset, inf), void();
int m = (l+r)/2;
if (L <= m) query(lc[o], L, R, i, l, m);
if (R > m) query(rc[o], L, R, i, m+1, r);
}
} T;
int sum, top, a[N], l[N], r[N], h[N];
inline void add(int x, int v)
{
if (v > 0) add(0, x, v), sum += v;
else add(x, 1, -v);
}
inline int hash_u(int x)
{
return upper_bound(h, h+top, x) - h;
}
inline int hash_l(int x)
{
return lower_bound(h, h+top, x) - h;
}
int main()
{
int n, ans = 0;
scanf("%d", &n);
offset = 2*n + 1;
rep (i, 1, n+1)
{
int b, w, p;
scanf("%d%d%d%d%d%d", a+i, &b, &w, l+i, r+i, &p);
ans += w;
add(2*i, b-w-p);
add(2*i+1, p);
add(2*i+1, 2*i, inf);
h[top++] = a[i];
}
sort(h, h+top);
top = unique(h, h+top) - h;
rep (i, 1, n+1)
{
l[i] = hash_l(l[i]);
r[i] = hash_u(r[i]) - 1;
a[i] = hash_l(a[i]);
T.query(T.rt[i-1], l[i], r[i], 2*i+1, 0, top-1);
T.insert(T.rt[i], T.rt[i-1], a[i], 2*i, 0, top-1);
}
printf("%d\n", sum - solver.solve(0, 1, 2 + 2*n + T.ptr) + ans);
return 0;
}