CF1408H 题解

First Post:

Last Update:

牛逼题，被教育了。

当时笔者看到这个题面就直接胡了一个贪心，发现假了之后改成了网络流，然后因模型过于复杂不会模拟流而宣告失败。事实上对于这题，简化问题和网络流建模是必不可少的两步。这题也告诉我们，模拟最大流时，一般将最大流转为最小割，然后用数据结构维护割边的方案。

设 为 的个数，那么答案上界显然为 。

也就是说，如果对于一个非零点，其某一边至少有 个 ，那么我们就不需要管这一边的匹配方案了，这边肯定是能匹配上的。

容易发现，每一个非零点的两边都至少有一边的 的个数大于 。

设 表示右边的零多于 的点的集合， 表示左边的零多于 的点的集合。

对于一种颜色，我们要选取一个非零点 作为三元组的中间点，显然如果 ，我们会把 尽可能的往右调整，否则会把 尽可能地往左调整。这样在保证一边 的个数大于 的同时，还最大化了另一边的 的个数。

所以对于一种颜色，我们可以处理出两个值 分别表示当 或 时， 的取值。

此时再进行网络流建模就简单很多了。

建三层图，一层表示所有颜色，一层表示所有非零点，一层表示所有零点。从 向所有颜色连边，每种颜色 向非零点 连边。所有非零点向其左边最靠右和右边最靠左的 连边。这些边的容量均为 。对于前 个 ，每个 连向它左边的第一个 ，容量为 。对于后 个 ，每个 连向它右边的第一个 ，容量为 。所有非零点向 连边，容量为 。

接下来开始求解这个网络流模型的最大流。因为要表示一组最大流的解十分困难，我们不妨将最大流转化为最小割，考虑割边的方案。容易发现，如果我们割从某个颜色 向 或 的连边，这显然是不如割 连向 的边优的。同理，我们也不会割非零点向零点连的边。所以，只有 向颜色连的边和所有零点向 连的边有可能被割掉。

如果说我们选择不割某一个颜色 ，那么 左边的 和 右边的 就必须全部割掉。容易发现，不管颜色怎么选，被割掉的 肯定是一段前缀和一段后缀。那我们枚举被割掉的前缀 ，维护每个后缀 被割掉的代价，显然是 中 的个数 减去 的颜色个数。使用一棵支持区间减，全局取 的线段树即可维护。

时间复杂度 。

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
#include <bits/stdc++.h>
using namespace std;

namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc
	#undef flush
}
using namespace FastIO;

const int N = 5e5 + 5;
int n;
int a[N];
int pre[N],suf[N];
int Lp[N],Rp[N];

int Mi[N << 2],tag[N << 2];
void pushup(int k) { Mi[k] = min(Mi[k << 1],Mi[k << 1 | 1]);}
void AddTag(int k,int v) { tag[k] += v;Mi[k] += v;}
void pushdown(int k) { if(tag[k]) AddTag(k << 1,tag[k]),AddTag(k << 1 | 1,tag[k]),tag[k] = 0;}
void modify(int k,int l,int r,int x,int y,int v)
{
	if(x <= l && r <= y) return AddTag(k,v);
	int mid = l + r >> 1;
	pushdown(k);
	if(x <= mid) modify(k << 1,l,mid,x,y,v);
	if(mid < y) modify(k << 1 | 1,mid + 1,r,x,y,v);
	pushup(k);
}
void build(int k,int l,int r)
{
	Mi[k] = tag[k] = 0;
	if(l == r) {Mi[k] = l;return;}
	int mid = l + r >> 1;
	build(k << 1,l,mid);build(k << 1 | 1,mid + 1,r);
	pushup(k);
}
bool vis[N];
inline void work()
{
	read(n);
	for(int i = 1;i <= n;i++) Lp[i] = Rp[i] = vis[i] = 0;
	for(int i = 1;i <= n;i++) read(a[i]),vis[a[i]] = 1;
	for(int i = 1;i <= n;i++) pre[i] = pre[i - 1] + (a[i] == 0);
	suf[n + 1] = 0;
	for(int i = n;i >= 1;i--) suf[i] = suf[i + 1] + (a[i] == 0);
	int lim = pre[n] / 2,L = 0,R = 0;
	for(int i = 1;i <= n;i++) if(pre[i] <= lim) L = i;
	R = L + 1;int col = 0;
	for(int i = 1;i <= n;i++) col += vis[i];
// 	printf("%d,%d\n",L,R);
	for(int i = 1;i <= L;i++) Lp[a[i]] = i;
	for(int i = n;i >= R;i--) Rp[a[i]] = i;
	int m = suf[R],ans = min(col,lim);build(1,0,m);
	for(int i = 1;i <= n;i++)
		if(vis[i] && !Lp[i])
		{
			modify(1,0,m,suf[Rp[i]],m,-1);
			ans = min(ans,col + Mi[1]);
		}
	for(int i = 1;i <= L;i++)
	{
		if(!a[i]) continue;
		if(Lp[a[i]] == i) modify(1,0,m,suf[Rp[a[i]]],m,-1);
		ans = min(ans,col + pre[i] + Mi[1]);
	}
	cout << ans << endl;
}
int main()
{
	int T;
	read(T);
	while(T--) work();
	return 0;
}
≡