CF1408H Rainbow Triples

CF1408H [* hard]

给定长度为 \(n\) 的序列 \(p\)

找出尽可能多的三元组 \((a_i,b_i,c_i)\) 满足:

  • \(1\le a_i<b_i<c_i\le n\)
  • \(a_i=c_i=0,b_i\ne 0\)
  • \(p_{b_i}\) 互不相同。
  • 所有的 \(a_i,b_i,c_i\) 互不相同。

输出最多可以选出多少个三元组,多组数据。

\(\sum n\le 5\cdot 10^5\)

Solution

神仙题,这个题太仙了。这里的做法可能和官方题解相比略为复杂。

设 \(z\) 为序列中 \(0\) 的数量,那么答案的上界为 \(\lfloor\frac{z}{2}\rfloor\)

假设一个位置左边有至少 \(\frac{z}{2}\) 个 \(0\),那么其左边一定可以选出来一个 \(0\) 来合成答案。同理于右边。

观察到每个点总会满足上述性质中的一条,那么根据此将节点划分为 L/R 两个集合,L 表示满足右边有至少 \(\frac{z}{2}\) 个 \(0\) 的点集,R 表示满足右边有至少 \(\frac{z}{2}\) 个 \(0\) 的点集。

对于每个颜色,假设其被选中,那么一定可以通过调整,使得其位于 L 集合中最右节点,或者 R 集合中最左节点(假设被选出的节点位于 L 集合,那么向右移动一定不会更劣)

这样对于每个颜色我们保留两个节点,分为 \((l,r)\)。

对于 \(r\) 元素,我们只需要考虑其右边的选择方案,对于 \(l\),只需要考虑其左边的选择方案,然后将合并的答案与 \(\frac{z}{2}\) 取 \(\min\) 即可。

  • 不难发现如果存在一种方案使得只对于 \(r\) 考虑右边能够匹配/只对于 \(l\) 考虑左边的情况下能够使得答案超过上界,那么一定存在方案达到上界。

这样弱化问题之后,我们考虑网络流建图:

让 \(S\) 向每个颜色连一条流量为 \(1\) 的边,对于 L 内的每个点向上一个点连边,R 内的每个点向下一个点连边,每个颜色向这两个点连边。

然后将所有 \(0\) 向 \(T\) 连边,不难发现此图上的最大流即为弱化问题的答案。

注意到最大流等于最小割,我们考虑从最小割的角度来统计答案,我们发现假设颜色 \(i\) 不被割去,那么前缀 \(0\) 和后缀 \(0\) 都必须被割去。

于是我们的割去方案一定是割走一段前缀 \(0\),割走一段后缀 \(0\),然后将部分颜色割走。

从左往右枚举前缀 \(0\) 割走的位置,对于每一段 R 中的后缀 \(0\),割走这一段后缀 \(0\) 的答案已经确定,即颜色总数减去他们包含的颜色数。通过线段树即可维护答案。

复杂度为 \(\mathcal O(n\log n)\)

\(Code:\)

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define pushup(x) (tr[x].mi = min( tr[ls(x)].mi, tr[rs(x)].mi ))
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int N = 5e5 + 5 ; 
int n, Col, a[N], pre[N], nxt[N], Z, vis[N] ; 
int L, R, m, Lw[N], Rw[N], Ans ; 
struct Tr {
	int mi, tag ;
} tr[N << 2] ;
void pushmark(int x) {
	int d = tr[x].tag ; 
	tr[ls(x)].tag += d, tr[rs(x)].tag += d, 
	tr[ls(x)].mi += d, tr[rs(x)].mi += d, tr[x].tag = 0 ; 
}
void update(int x, int l, int r, int ql, int qr) {
	if( ql <= l && r <= qr ) return -- tr[x].tag, -- tr[x].mi, void() ;
	if( r < ql || qr < l ) return ; 
	int mid = (l + r) >> 1 ; pushmark(x) ;
	update(ls(x), l, mid, ql, qr), update(rs(x), mid + 1, r, ql, qr), pushup(x) ;
}
void build(int x, int l, int r) {
	if( l == r ) return tr[x].mi = l, void() ; 
	int mid = (l + r) >> 1 ; 
	build(ls(x), l, mid), build(rs(x), mid + 1, r), pushup(x) ;
}
void solve() {
	n = gi() ; 
	rep( i, 1, n ) a[i] = gi(), vis[a[i]] = 1 ; 
	rep( i, 1, n ) pre[i] = pre[i - 1] + (a[i] == 0) ;
	drep( i, 1, n ) nxt[i] = nxt[i + 1] + (a[i] == 0) ;
	Z = pre[n] / 2, Ans = Z, L = 0, R = 0 ; 
	rep( i, 1, n ) if( pre[i] <= Z ) ++ L ; 
	R = L + 1, Col = 0 ; 
	rep( i, 1, n ) if( vis[i] ) ++ Col ; 
	rep( i, 1, n ) Rw[i] = n + 1 ; 
	rep( i, 1, L ) Lw[a[i]] = i ; 
	drep( i, R, n ) Rw[a[i]] = i ; 
	m = nxt[R], build(1, 0, m), Ans = min(Ans, Col) ; 
	rep( i, 1, n ) if( vis[i] && (!Lw[i]) ) {
		update(1, 0, m, nxt[Rw[i]], m) ; 
		Ans = min(Ans, Col + tr[1].mi ) ; 
	} 
	for(re int i = 1; i <= L; ++ i) {
		int u = a[i] ; 
		if( Lw[u] == i ) {
			update(1, 0, m, nxt[Rw[u]], m) ; 
			Ans = min(Ans, Col + tr[1].mi + pre[i]) ; 
		}
	}
	cout << Ans << endl ; 
	rep( i, 1, n ) pre[i] = nxt[i] = Lw[i] = Rw[i] = vis[i] = 0 ;
	rep( i, 1, n * 4 ) tr[i].mi = tr[i].tag = 0 ;  
}
signed main()
{
	int T = gi() ; 
	while( T-- ) solve() ;  
	return 0 ;
}
上一篇:C#8.0新特性


下一篇:纯纯的css画美美的彩虹