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 ;
}