题面

背景

题目描述

从前有个

n

n

n 个方格排成一行，从左至右依此编号为

1

,

2

,

⋯

,

n

1,2,⋯,n

1,2,⋯,n。

有一天思考熊想给这

n

n

n 个方格染上黑白两色。

第

i

i

i 个方格上有

6

6

6 个属性：

a

i

,

b

i

,

w

i

,

l

i

,

r

i

,

p

i

a_i,b_i,w_i,l_i,r_i,p_i

ai​,bi​,wi​,li​,ri​,pi​。

如果方格

i

i

i 染成黑色就会获得

b

i

b_i

bi​ 的好看度。

如果方格

i

i

i 染成白色就会获得

w

i

w_i

wi​ 的好看度。

但是太多了黑色就不好看了。如果方格

i

i

i 是黑色，并且存在一个

j

j

j 使得

1

≤

j

<

i

1≤j<i

1≤j<i 且

l

i

≤

a

j

≤

r

i

l_i≤a_j≤r_i

li​≤aj​≤ri​ 且方格

j

j

j 为白色，那么方格

i

i

i 就被称为奇怪的方格。

如果方格

i

i

i 是奇怪的方格，就会使总好看度减少

p

i

p_i

pi​。

也就是说对于一个染色方案，好看度为：

∑

方格 i 为黑色

b

i

+

∑

方格 i 为白色

w

i

−

∑

方格 i 为奇怪的方格

p

i

∑_\text{方格 i 为黑色}b_i+∑_\text{方格 i 为白色}w_i−∑_\text{方格 i 为奇怪的方格}p_i

方格 i 为黑色∑​bi​+方格 i 为白色∑​wi​−方格 i 为奇怪的方格∑​pi​

现在给你

n

,

a

,

b

,

w

,

l

,

r

,

p

n,a,b,w,l,r,p

n,a,b,w,l,r,p，问所有染色方案中最大的好看度是多少。

数据范围

设

a

m

a

x

a_{max}

amax​ 为

a

,

l

,

r

a,l,r

a,l,r 中的最大值，

v

m

a

x

v_{max}

vmax​ 为

b

,

w

b,w

b,w 中的最大值,

p

m

a

x

p_{max}

pmax​ 为

p

p

p 中的最大值。

测试点编号	n n n	a m a x a_{max} amax​	v m a x v_{max} vmax​	p m a x p_{max} pmax​
1 1 1	= 5 =5 =5	≤ 10 ≤10 ≤10	≤ 10 ≤10 ≤10	≤ 10 ≤10 ≤10
2 2 2	= 20 =20 =20	≤ 40 ≤40 ≤40	≤ 40 ≤40 ≤40	≤ 40 ≤40 ≤40
3 3 3	= 20 =20 =20	≤ 40 ≤40 ≤40	≤ 40 ≤40 ≤40	≤ 40 ≤40 ≤40
4 4 4	= 5000 =5000 =5000	≤ 10 ≤10 ≤10	≤ 200000 ≤200000 ≤200000	≤ 100000 ≤100000 ≤100000
5 5 5	= 5000 =5000 =5000	≤ 10 ≤10 ≤10	≤ 200000 ≤200000 ≤200000	≤ 300000 ≤300000 ≤300000
6 6 6	= 200 =200 =200	≤ 109 ≤109 ≤109	≤ 200000 ≤200000 ≤200000	≤ 200000 ≤200000 ≤200000
7 7 7	= 300 =300 =300	≤ 109 ≤109 ≤109	≤ 200000 ≤200000 ≤200000	≤ 220000 ≤220000 ≤220000
8 8 8	= 500 =500 =500	≤ 109 ≤109 ≤109	≤ 200000 ≤200000 ≤200000	≤ 400000 ≤400000 ≤400000
9 9 9	= 5000 =5000 =5000	≤ 5000 ≤5000 ≤5000	≤ 200000 ≤200000 ≤200000	≤ 150000 ≤150000 ≤150000
10 10 10	= 5000 =5000 =5000	≤ 109 ≤109 ≤109	≤ 200000 ≤200000 ≤200000	≤ 300000 ≤300000 ≤300000

2
 

s

,

48
 

M

B

\tt 2\,s~~,~~48\,MB

2s  ,  48MB

题解

最大的好看度，可以转化为：总好看度（含 b,w） - 最小损失好看度（含 b,w,p）

于是，可以用网络流最小割解决“最小损失好看度”的问题。

令

S

,

T

S,T

S,T 为源点、汇点，

S

S

S 部表示涂黑色，

T

T

T 部表示涂白色。
我们把每个点

i

i

i 连两条边：

S

→

i

S\rightarrow i

S→i（边权为

b

i

b_i

bi​，若保留，则表示

i

i

i 涂黑色），

i

→

T

i\rightarrow T

i→T（边权为

w

i

w_i

wi​ ，若保留，则表示

i

i

i 涂白色）。
对于每个

i

i

i ，新建一个点

i

′

i'

i′，与每个满足

1

≤

j

<

i

,

l

i

≤

a

j

≤

r

i

1\leq j<i,l_i\leq a_j\leq r_i

1≤j<i,li​≤aj​≤ri​ 的

j

j

j 连一条边

i

′

→

j

i'\rightarrow j

i′→j （边权为

+

∞

+\infty

+∞），然后连一条边

i

→

i

′

i\rightarrow i'

i→i′（边权为

p

i

p_i

pi​），这样，如果所有的

j

j

j 有任意一个是白色（

j

→

T

j\rightarrow T

j→T 保留），为了使

S

,

T

S,T

S,T 不可达，就必须保留

i

→

T

i\rightarrow T

i→T 断掉

S

→

i

S\rightarrow i

S→i（选白色），或者保留

S

→

i

S\rightarrow i

S→i 断掉

i

→

i

′

i\rightarrow i'

i→i′ （选黑色，但是多付出

p

i

p_i

pi​ 的代价）。

虽然建图可以随便完成，但是边的数量太多，不仅空间存不下（48 Mb），而且最大流会超时。

于是我们可以优化建图。

我们建立新点

i

′

i'

i′ 的目的，其实是要使得存在这么一个点，通过若干容量为无穷的边，可以只到达所有符合

1

≤

j

<

i

,

l

i

≤

a

j

≤

r

i

1\leq j<i,l_i\leq a_j\leq r_i

1≤j<i,li​≤aj​≤ri​ 的

j

j

j。但是，不同的

i

′

i'

i′ ，可能连向一大批相同的

j

j

j ，

j

j

j 和

a

j

a_j

aj​ 都是连续在一个范围内的。

线段树优化建图

瞎扯了这么多，我也不绕弯了，用线段树优化建图。每次的

i

′

i'

i′ 只需要连向线段树上的某些（log的数量级）区间点，每个父亲向左右儿子连容量无穷的边，每个叶子向

a

j

a_j

aj​ 等于某一值的所有

j

j

j 连容量无穷的边。

有两个条件，

1

≤

j

<

i

1\leq j<i

1≤j<i 和

l

i

≤

a

j

≤

r

i

l_i\leq a_j\leq r_i

li​≤aj​≤ri​ ，难道要树套树？

其实只用可持久化线段树就行了。

分块优化建图

n

≤

5000

n\leq 5000

n≤5000 ，貌似有点小？根号和 log 差不太多啊。

可持久化分块，何如？每次只用新建 1~2 个点，边数也不用如此繁多。

实际上比线段树优秀得多：

CODE

线段树

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<ctime>

#include<queue>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 5005

#define LL long long

#define ULL unsigned long long

#define UI unsigned int

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) (-(x) & (x))

#define FI first

#define SE second

#define eps (1e-4)

#define SI(x) set<x>::iterator

#define MI map<int,int>::iterator

#define SQ 51

//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

//#pragma GCC optimize("Ofast")

LL read() {

	LL f=1,x=0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f*x;

}

void putpos(LL x) {

	if(!x) return ;

	putpos(x/10); putchar('0'+(x%10));

}

void putnum(LL x) {

	if(!x) putchar('0');

	else if(x < 0) putchar('-'),putpos(-x);

	else putpos(x);

}

void AIput(LL x,char c) {putnum(x);putchar(c);}

int n,m,s,o,k;

int cnp,hd[MAXN*200],S,T;

int v[MAXN*400],nx[MAXN*400],rev[MAXN*400],cne;

LL w[MAXN*400];

int ins(int x,int y,LL k) {

	if(!x || !y) return 0;

	nx[++ cne] = hd[x];v[cne] = y;w[cne] = k;hd[x] = cne;

	nx[++ cne] = hd[y];v[cne] = x;w[cne] = 0;hd[y] = cne;

	rev[cne] = cne-1; rev[cne-1] = cne; return cne-1;

}

int hd2[MAXN*200],d[MAXN*200];

bool bfs(int S,int T) {

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

		hd2[i] = hd[i]; d[i] = -1;

	}

	queue<int> b;

	d[S] = 0;

	b.push(S);

	while(!b.empty()) {

		int t = b.front();b.pop();

		if(t == T) return 1;

		for(int i = hd[t];i;i = nx[i]) {

			if(d[v[i]] < 0 && w[i] > 0) {

				d[v[i]] = d[t] + 1;

				b.push(v[i]);

			}

		}

	}

	return 0;

}

LL dfs(int x,LL flow) {

	if(x == T) return flow;

	LL res = 0;

	for(int i = hd2[x];i;i = nx[i]) {

		if(d[v[i]] == d[x] + 1 && w[i] > 0) {

			LL mx = dfs(v[i],min(flow-res,w[i]));

			res += mx; w[i] -= mx; w[rev[i]] += mx;

			if(res == flow) break;

		}

		hd2[x] = nx[i];

	}

	return res;

}

LL dinic(int S,int T) {

	LL ans = 0;

	while(bfs(S,T)) {

		ans += dfs(S,(LL)1e18);

	}return ans;

}

int A[MAXN],bk[MAXN],we[MAXN],ll[MAXN],rr[MAXN],P[MAXN];

int ar[MAXN];

int tre[MAXN<<2],M;

void maketree(int n) {

	M=1;while(M<n+2)M<<=1;

}

void addtree(int x,int y) {

	int s=M+x;ins(++ cnp,tre[s],(LL)1e18);

	tre[s] = cnp;ins(tre[s],y,(LL)1e18);s >>= 1;

	while(s) {

		tre[s] = ++ cnp;

		ins(tre[s],tre[s<<1],(LL)1e18);

		ins(tre[s],tre[s<<1|1],(LL)1e18);

		s >>= 1;

	}return ;

}

int buildp(int l,int r) {

	int p = ++ cnp;

	int s = M+l-1,t = M+r+1;

	while(s || t) {

		if((s>>1) ^ (t>>1)) {

			if(!(s&1)) ins(p,tre[s^1],(LL)1e18);

			if(t & 1) ins(p,tre[t^1],(LL)1e18);

		}else break;

		s >>= 1;t >>= 1;

	}return p;

}

int main() {

	n = read();

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

	LL ans = 0;

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

		A[i] = read(); ar[i] = A[i];

		bk[i] = read(); we[i] = read();

		ll[i] = read(); rr[i] = read();

		P[i] = read();

		ins(S,i,bk[i]); ins(i,T,we[i]);

		ans += we[i]+bk[i];

	}

	sort(ar + 1,ar + 1 + n);

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

		A[i] = lower_bound(ar + 1,ar + 1 + n,A[i]) - ar;

		ll[i] = lower_bound(ar + 1,ar + 1 + n,ll[i]) - ar;

		rr[i] = lower_bound(ar + 1,ar + 1 + n,rr[i]+1) - ar - 1;

	}

	maketree(n);

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

		int p = buildp(ll[i],rr[i]);

		ins(i,p,P[i]);

		addtree(A[i],i);

	}

	ans -= dinic(S,T);

	AIput(ans,'\n');

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

//		printf("%d(%d): ",i,A[i]);

//		if(w[fr[i]] > 0) {

//			printf("black");

//		}

//		else printf("white");

//		printf("   [%d,%d]\n",ll[i],rr[i]);

//	}

	return 0;

}

分块

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<ctime>

#include<queue>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 5005

#define LL long long

#define ULL unsigned long long

#define UI unsigned int

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) (-(x) & (x))

#define FI first

#define SE second

#define eps (1e-4)

#define SI(x) set<x>::iterator

#define MI map<int,int>::iterator

#define SQ 51

//#pragma GCC optimize(2)

//#pragma GCC optimize(3)

//#pragma GCC optimize("Ofast")

LL read() {

	LL f=1,x=0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f*x;

}

void putpos(LL x) {

	if(!x) return ;

	putpos(x/10); putchar('0'+(x%10));

}

void putnum(LL x) {

	if(!x) putchar('0');

	else if(x < 0) putchar('-'),putpos(-x);

	else putpos(x);

}

void AIput(LL x,char c) {putnum(x);putchar(c);}

int n,m,s,o,k;

int cnp,hd[MAXN*200],S,T;

int v[MAXN*400],nx[MAXN*400],rev[MAXN*400],cne;

LL w[MAXN*400];

int ins(int x,int y,LL k) {

	if(!x || !y) return 0;

	nx[++ cne] = hd[x];v[cne] = y;w[cne] = k;hd[x] = cne;

	nx[++ cne] = hd[y];v[cne] = x;w[cne] = 0;hd[y] = cne;

	rev[cne] = cne-1; rev[cne-1] = cne; return cne-1;

}

int hd2[MAXN*200],d[MAXN*200];

bool bfs(int S,int T) {

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

		hd2[i] = hd[i]; d[i] = -1;

	}

	queue<int> b;

	d[S] = 0;

	b.push(S);

	while(!b.empty()) {

		int t = b.front();b.pop();

		if(t == T) return 1;

		for(int i = hd[t];i;i = nx[i]) {

			if(d[v[i]] < 0 && w[i] > 0) {

				d[v[i]] = d[t] + 1;

				b.push(v[i]);

			}

		}

	}

	return 0;

}

LL dfs(int x,LL flow) {

	if(x == T) return flow;

	LL res = 0;

	for(int i = hd2[x];i;i = nx[i]) {

		if(d[v[i]] == d[x] + 1 && w[i] > 0) {

			LL mx = dfs(v[i],min(flow-res,w[i]));

			res += mx; w[i] -= mx; w[rev[i]] += mx;

			if(res == flow) break;

		}

		hd2[x] = nx[i];

	}

	return res;

}

LL dinic(int S,int T) {

	LL ans = 0;

	while(bfs(S,T)) {

		ans += dfs(S,(LL)1e18);

	}return ans;

}

int bl[MAXN],cnb,tt[MAXN];

int A[MAXN],bk[MAXN],we[MAXN],ll[MAXN],rr[MAXN],P[MAXN];

int ar[MAXN];

int buildp(int l,int r) {

	int s = l/SQ+1,t = r/SQ+1;

	int p = ++ cnp;

	if(s == t) {

		for(int i = l;i <= r;i ++) ins(p,tt[i],(LL)1e18);

	}

	else {

		for(int i = l;(i/SQ+1) == s;i ++) ins(p,tt[i],(LL)1e18);

		for(int i = r;(i/SQ+1) == t;i --) ins(p,tt[i],(LL)1e18);

		for(int i = s+1;i < t;i ++) {

			ins(p,bl[i],(LL)1e18);

		}

	}return p;

}

int main() {

	n = read();

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

	LL ans = 0;

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

		A[i] = read(); ar[i] = A[i];

		bk[i] = read(); we[i] = read();

		ll[i] = read(); rr[i] = read();

		P[i] = read();

		ins(S,i,bk[i]); ins(i,T,we[i]);

		ans += we[i]+bk[i];

	}

	sort(ar + 1,ar + 1 + n);

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

		A[i] = lower_bound(ar + 1,ar + 1 + n,A[i]) - ar;

		ll[i] = lower_bound(ar + 1,ar + 1 + n,ll[i]) - ar;

		rr[i] = lower_bound(ar + 1,ar + 1 + n,rr[i]+1) - ar - 1;

	}

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

		int p = buildp(ll[i],rr[i]);

		ins(i,p,P[i]);

		int B = A[i]/SQ+1; cnb = max(cnb,B);

		ins(++ cnp,bl[B],(LL)1e18);

		bl[B] = cnp;

		ins(bl[B],i,(LL)1e18);

		ins(++ cnp,tt[A[i]],(LL)1e18);

		tt[A[i]] = cnp;

		ins(tt[A[i]],i,(LL)1e18);

	}

	ans -= dinic(S,T);

	AIput(ans,'\n');

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

//		printf("%d(%d): ",i,A[i]);

//		if(w[fr[i]] > 0) {

//			printf("black");

//		}

//		else printf("white");

//		printf("   [%d,%d]\n",ll[i],rr[i]);

//	}

	return 0;

}

UOJ#XX A+B Problem （罔烙硫）的相关教程结束。