BZOJ-3267. KC采花

Posted by miskcoo on December 10, 2014

这题是 bzoj-3267 上的题目,原题大概是给一列数,要求支持操作:

  • 修改某个数的值
  • 读入 l、r、k,询问在 [l,r] 内选不相交的不超过 k 个子段,最大的和是多少

然后序列的长度和操作的次数大约都在 $10^5$ 级别的

首先可能会想到 k = 1 的情况,也就是用线段树维护,记录某个区间靠右边的最大值,靠左边的最大值以及答案和区间和,这样的话才可以有足够的信息在线段树中合并两个区间

具体的做法是这样的

对于两个区间,它们合并之后的新区间靠左边的最大值有两种可能,一是原先左边的区间靠左的最大值,二是原先左边的区间的和加上右边区间靠左边的最大值,另外两个部分也是相同的,这样的话一次询问是 $\Theta(\log n)$ 的

那么,回到原题之后,要求选择 k 个不相交的子段,也会想到用线段树直接维护 k 个这样的东西然后 $\Theta(k^2\log n)$ 维护,但是这题肯定是过不了的

但是,看到这题选出一个最大子区间,会想到一种最长路的做法,也就是建立一个源、一个汇,源向所有点连边权为 0 的边,所有点向汇连边权为自身边权的边,然后每个点向右边的一个点连一条自身边权的边,最后源向汇连一条边权为 0 的边(不取任何区间的时候),然后跑最长路

这样变成 k 个区间的时候改成费用流就可以做了,可是这样做跑得会比暴力还慢

考虑这都有什么操作,一个是增广,一次增广也就是找一段最大的子段,然后是要支持退流,也就等于把找到的最大子段整段权值变为相反数,这样的话前一个操作刚刚的线段树已经有了,至于后面一个操作,因为是线段树,可以直接加上区间取相反数的支持,然后这题复杂度就变为 $\Theta(km\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
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include <cstdio>
#include <algorithm>

const int MaxN = 100010;
struct range_t
{
	int l, r, v;
	range_t& operator = (int rhs)
	{
		v = rhs;
		return *this;
	}
};

struct node_t
{
	range_t left, right;
	range_t ans;
	int sum;

	void reverse() {
		sum = -sum;
		ans.v = -ans.v;
		left.v = -left.v;
		right.v = -right.v;
	}
};

int modify_pos, modify_val;
int lazy[MaxN * 4];
node_t node[MaxN * 4], node_m[MaxN * 4];

bool max_cmp(int a, int b) { return a > b; }
bool min_cmp(int a, int b) { return a < b; }

template<typename Comparer>
node_t& merge(node_t& t, const node_t& a, const node_t& b, Comparer cmp)
{
	// merge left
	t.left = a.left;
	if(cmp(a.sum + b.left.v, t.left.v))
	{
		t.left = a.sum + b.left.v;
		t.left.r = b.left.r;
	}

	// merge right
	t.right = b.right;
	if(cmp(a.right.v + b.sum, t.right.v))
	{
		t.right = a.right.v + b.sum;
		t.right.l = a.right.l;
	}

	// merge ans
	t.ans = cmp(a.ans.v, b.ans.v) ? a.ans : b.ans;
	if(cmp(a.right.v + b.left.v, t.ans.v))
	{
		t.ans.v = a.right.v + b.left.v;
		t.ans.l = a.right.l;
		t.ans.r = b.left.r;
	}

	// merge sum
	t.sum = a.sum + b.sum;
	return t;
}

void pushdown(int now, int head, int tail)
{
	if(!lazy[now]) return;
	int l = now << 1, r = l + 1;
	if(head != tail)
		lazy[l] ^= 1, lazy[r] ^= 1;
	lazy[now] = 0;

	node_t& max = node[now], &min = node_m[now];
	std::swap(max, min);
	max.reverse();
	min.reverse();
}

void modify(int now, int head, int tail)
{
	pushdown(now, head, tail);
	if(head == tail)
	{
		node[now].left = node[now].right = modify_val;
		node[now].ans = node[now].sum = modify_val;
		node_m[now] = node[now];
		return;
	}

	int m = (head + tail) >> 1;
	int l = now << 1, r = l + 1;
	if(modify_pos <= m) modify(l, head, m);
	else modify(r, m + 1, tail);

	merge(node[now], node[l], node[r], max_cmp);
	merge(node_m[now], node_m[l], node_m[r], min_cmp);
}

node_t ask(int now, int head, int tail, int l, int r)
{
	pushdown(now, head, tail);
	if(head == l && tail == r)
		return node[now];

	int m = (head + tail) >> 1;
	if(r <= m) return ask(now << 1, head, m, l, r);
	if(l > m) return ask((now << 1) + 1, m + 1, tail, l, r);

	node_t t1 = ask(now << 1, head, m, l, m);
	node_t t2 = ask((now << 1) + 1, m + 1, tail, m + 1, r);
	node_t ans = node[now];
	return merge(ans, t1, t2, max_cmp);
}

void reverse(int now, int head, int tail, int a, int b)
{
	if(head == a && tail == b)
	{
		lazy[now] ^= 1;
		pushdown(now, head, tail);
		return;
	}

	pushdown(now, head, tail);
	int m = (head + tail) >> 1;
	int l = now << 1, r = l + 1;
	bool flag = true;
	if(b <= m) 
	{
		flag = false;
		reverse(l, head, m, a, b);
		pushdown(r, m + 1, tail);
	}
	
	if(a > m) 
	{
		flag = false;
		reverse(r, m + 1, tail, a, b);
		pushdown(l, head, m);
	}

	if(flag)
	{
		reverse(l, head, m, a, m);
		reverse(r, m + 1, tail, m + 1, b);
	}

	merge(node[now], node[l], node[r], max_cmp);
	merge(node_m[now], node_m[l], node_m[r], min_cmp);
}

void build_tree(int now, int l, int r)
{
	if(l == r)
	{
		int v;
		std::scanf("%d", &v);
		node[now].ans = node[now].sum = v;
		node[now].ans.l = node[now].ans.r = l;
		node[now].left = node[now].right = node[now].ans;
		node_m[now] = node[now];
		return;
	}

	int m = (l + r) >> 1;
	int a = now << 1, b = a + 1;
	build_tree(a, l, m);
	build_tree(b, m + 1, r);
	merge(node[now], node[a], node[b], max_cmp);
	merge(node_m[now], node_m[a], node_m[b], min_cmp);
}

int stack[20][2];
int main()
{
	int n, m;
	std::scanf("%d", &n);
	build_tree(1, 1, n);
	std::scanf("%d", &m);
	while(m --> 0)
	{
		int oper;
		std::scanf("%d", &oper);
		if(oper == 0)
		{
			std::scanf("%d %d", &modify_pos, &modify_val);
			modify(1, 1, n);
		} else {
			int l, r, k;
			std::scanf("%d %d %d", &l, &r, &k);

			int ans = 0, stop = 0;
			for(int i = 0; i != k; ++i)
			{
				node_t ret = ask(1, 1, n, l, r);
				if(ret.ans.v <= 0) break;

				ans += ret.ans.v;
				if(i + 1 != k)
				{
					reverse(1, 1, n, ret.ans.l, ret.ans.r);
					stack[stop][0] = ret.ans.l;
					stack[stop++][1] = ret.ans.r;
				}
			}

			std::printf("%d\n", ans);

			for(int i = 0; i != stop; ++i)
				reverse(1, 1, n, stack[i][0], stack[i][1]);
		}
	}
	return 0;
}