最大m子段和问题

OI/XCPC , Comments

普通版

题目大意

  一个长度为 $n$ 的序列 $a_1…a_n$，让你从中选出 $m$ 个连续段，使得选出来的和最大。

【$O(nm)$】

  设 $f_{i,j}$ 表示前 $i$ 个数，共选了 $j$ 个连续段，所得到的最大和。
  设 $g_{i,j}=\max\{ f_{1..i, j} \}$， 设 $S$ 表示 $a$ 的前缀和。

  然后搞一下就是 $O(nm)$ 的了。

【$O(m \log n)$】

  源点向每一个点 $i$ 连一条容量为 $1$、费用为 $a_i$ 的边，每个点 $i$ 向 $i+1$ 连一条容量为 $1$、费用为 $a_{i+1}$ 的边，每个点向汇点连一条容量为 $1$、费用为 $0$ 的边。
  这样建图，每增广一次，相当于取出了一个连续段，又由于有反向弧这种操作，所以直接增广 $m$ 次就可以了。（当然，如果增广出来是负数，可以直接退出）

  当然直接跑费用流肯定会 T。
  引入费用流只是为了引入反向弧这种机制。我们发现实际上是每次贪心地选取一个最大子段而已，那么选完之后我们就把这段取反就行了。
  这个用线段树实现，维护的变量挺多的。

加强版

题目大意

  给你一个长度为 $n$ 的序列 $a_1…a_n$，有如下两种操作：
  $1~x~y$：将 $a_x$ 的值改为 $y$
  $2~l~r~k$：询问区间 $[l, r]$ 的最大 $k$ 子段和。

【$O(m \log n)$】

  像上面那样，既然都已经打了个线段树了，那就再加个单点修改。

代码

普通

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=5e4+5;

struct TR{
	LL s,sl,sr,st;
	int wzi,wzj,wzl,wzr;
};

int n,m;
LL a[maxn];

TR tr[2][4*maxn];
bool bz[4*maxn];
TR merge(TR a,TR b)
{
	TR re;
	re.s=a.s+b.s;
	
	if (a.st>b.st)
	{
		re.st=a.st;
		re.wzi=a.wzi, re.wzj=a.wzj;
	} else
	{
		re.st=b.st;
		re.wzi=b.wzi, re.wzj=b.wzj;
	}
	if (a.sr+b.sl>re.st)
	{
		re.st=a.sr+b.sl;
		re.wzi=a.wzr, re.wzj=b.wzl;
	}
	
	if (a.sl>a.s+b.sl)
	{
		re.sl=a.sl;
		re.wzl=a.wzl;
	} else
	{
		re.sl=a.s+b.sl;
		re.wzl=b.wzl;
	}
	
	if (b.sr>b.s+a.sr)
	{
		re.sr=b.sr;
		re.wzr=b.wzr;
	} else
	{
		re.sr=b.s+a.sr;
		re.wzr=a.wzr;
	}
	
	return re;
}
void tr_js(int k,int l,int r)
{
	if (l==r)
	{
		tr[0][k].s=tr[0][k].sl=tr[0][k].sr=tr[0][k].st=a[l];
		tr[0][k].wzi=tr[0][k].wzj=tr[0][k].wzl=tr[0][k].wzr=l;
		tr[1][k].s=tr[1][k].sl=tr[1][k].sr=tr[1][k].st=-a[l];
		tr[1][k].wzi=tr[1][k].wzj=tr[1][k].wzl=tr[1][k].wzr=l;
		return;
	}
	int t=k<<1, t1=(l+r)>>1;
	tr_js(t,l,t1), tr_js(t+1,t1+1,r);
	tr[0][k]=merge(tr[0][t],tr[0][t+1]);
	tr[1][k]=merge(tr[1][t],tr[1][t+1]);
}
void update(int k,int t)
{
	if (!bz[k]) return;
	swap(tr[0][t],tr[1][t]);
	swap(tr[0][t+1],tr[1][t+1]);
	bz[t]^=bz[k];
	bz[t+1]^=bz[k];
	bz[k]=0;
}
void xg_many(int k,int l,int r,int x,int y)
{
	if (l==x && r==y)
	{
		swap(tr[0][k],tr[1][k]);
		bz[k]^=1;
		return;
	}
	int t=k<<1, t1=(l+r)>>1;
	update(k,t);
	if (y<=t1) xg_many(t,l,t1,x,y);
		else if (x>t1) xg_many(t+1,t1+1,r,x,y);
			else xg_many(t,l,t1,x,t1), xg_many(t+1,t1+1,r,t1+1,y);
	tr[0][k]=merge(tr[0][t],tr[0][t+1]);
	tr[1][k]=merge(tr[1][t],tr[1][t+1]);
}

LL get(int m)
{
	LL re=0;
	while (m--)
	{
		if (tr[0][1].st<0) break;
		re+=tr[0][1].st;
		xg_many(1,1,n,tr[0][1].wzi,tr[0][1].wzj);
	}
	return re;
}

int main()
{
	scanf("%d %d",&n,&m);
	fo(i,1,n) scanf("%lld",&a[i]);
	tr_js(1,1,n);
	
	printf("%lld\n",get(m));
}

加强

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=1e5+5;

struct TR{
	int s,sl,sr,st,wzi,wzj,wzl,wzr;
};

int n,a[maxn];

TR tr[2][4*maxn];
bool bz[4*maxn];
TR merge(TR a,TR b)
{
	TR re;
	re.s=a.s+b.s;
	
	if (a.st>b.st)
	{
		re.st=a.st;
		re.wzi=a.wzi, re.wzj=a.wzj;
	} else
	{
		re.st=b.st;
		re.wzi=b.wzi, re.wzj=b.wzj;
	}
	if (a.sr+b.sl>re.st)
	{
		re.st=a.sr+b.sl;
		re.wzi=a.wzr, re.wzj=b.wzl;
	}
	
	if (a.sl>a.s+b.sl)
	{
		re.sl=a.sl;
		re.wzl=a.wzl;
	} else
	{
		re.sl=a.s+b.sl;
		re.wzl=b.wzl;
	}
	
	if (b.sr>b.s+a.sr)
	{
		re.sr=b.sr;
		re.wzr=b.wzr;
	} else
	{
		re.sr=b.s+a.sr;
		re.wzr=a.wzr;
	}
	
	return re;
}
void tr_js(int k,int l,int r)
{
	if (l==r)
	{
		tr[0][k].s=tr[0][k].sl=tr[0][k].sr=tr[0][k].st=a[l];
		tr[0][k].wzi=tr[0][k].wzj=tr[0][k].wzl=tr[0][k].wzr=l;
		tr[1][k].s=tr[1][k].sl=tr[1][k].sr=tr[1][k].st=-a[l];
		tr[1][k].wzi=tr[1][k].wzj=tr[1][k].wzl=tr[1][k].wzr=l;
		return;
	}
	int t=k<<1, t1=(l+r)>>1;
	tr_js(t,l,t1), tr_js(t+1,t1+1,r);
	tr[0][k]=merge(tr[0][t],tr[0][t+1]);
	tr[1][k]=merge(tr[1][t],tr[1][t+1]);
}
void update(int k,int t)
{
	if (!bz[k]) return;
	swap(tr[0][t],tr[1][t]);
	swap(tr[0][t+1],tr[1][t+1]);
	bz[t]^=bz[k];
	bz[t+1]^=bz[k];
	bz[k]=0;
}
void xg_single(int k,int l,int r,int x,int z)
{
	if (l==r)
	{
		tr[0][k].s=tr[0][k].sl=tr[0][k].sr=tr[0][k].st=z;
		tr[1][k].s=tr[1][k].sl=tr[1][k].sr=tr[1][k].st=-z;
		return;
	}
	int t=k<<1, t1=(l+r)>>1;
	update(k,t);
	if (x<=t1) xg_single(t,l,t1,x,z); else xg_single(t+1,t1+1,r,x,z);
	tr[0][k]=merge(tr[0][t],tr[0][t+1]);
	tr[1][k]=merge(tr[1][t],tr[1][t+1]);
}
void xg_many(int k,int l,int r,int x,int y)
{
	if (l==x && r==y)
	{
		swap(tr[0][k],tr[1][k]);
		bz[k]^=1;
		return;
	}
	int t=k<<1, t1=(l+r)>>1;
	update(k,t);
	if (y<=t1) xg_many(t,l,t1,x,y);
		else if (x>t1) xg_many(t+1,t1+1,r,x,y);
			else xg_many(t,l,t1,x,t1), xg_many(t+1,t1+1,r,t1+1,y);
	tr[0][k]=merge(tr[0][t],tr[0][t+1]);
	tr[1][k]=merge(tr[1][t],tr[1][t+1]);
}
TR tr_cx(int k,int l,int r,int x,int y)
{
	if (l==x && r==y) return tr[0][k];
	int t=k<<1, t1=(l+r)>>1;
	update(k,t);
	if (y<=t1) return tr_cx(t,l,t1,x,y);
		else if (x>t1) return tr_cx(t+1,t1+1,r,x,y);
			else return merge(tr_cx(t,l,t1,x,t1), tr_cx(t+1,t1+1,r,t1+1,y));
}

int z[maxn][2],z0;
int get(int m,int l,int r)
{
	int re=0;
	while (m--)
	{
		TR t=tr_cx(1,1,n,l,r);
		if (t.st<=0) break;
		re+=t.st;
		z[++z0][0]=t.wzi, z[z0][1]=t.wzj;
		xg_many(1,1,n,t.wzi,t.wzj);
	}
	for(; z0; z0--) xg_many(1,1,n,z[z0][0],z[z0][1]);
	return re;
}

int m;
int main()
{
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&a[i]);
	tr_js(1,1,n);
	
	scanf("%d",&m);
	while (m--)
	{
		int ty,l,r,k;
		scanf("%d %d %d",&ty,&l,&r);
		if (ty==0)
		{
			xg_single(1,1,n,l,r);
		} else
		{
			scanf("%d",&k);
			printf("%d\n",get(k,l,r));
		}
	}
}

kqpOIACMer / HKU_CS / LLer / TCS

糖少许，盐少许