题解 CF1408H 【Rainbow Triples】

s_r_f · 2020-10-02 23:44:43 · 题解

记 0 的个数为 cntz , 不难发现答案有一个上界为 \lfloor \frac{cntz}{2}\rfloor .

考虑把序列分为两个部分， L 和 R , 满足 L 部分中的点右边都有 \geq \lfloor \frac{cntz}{2}\rfloor 个 0 , 而 R 部分中的点左边都有 \geq \lfloor \frac{cntz}{2}\rfloor 个 0 , 那么 L 部分只需要考虑在左边的匹配， R 部分只需要考虑在右边的匹配即可 ， 最后答案需要对 \geq \lfloor \frac{cntz}{2}\rfloor 取 \min .

不难发现，对于每个权值只需要在 L 中保留其最靠右的点 l_x , 在 R 中只需要保留其最靠左的点 r_x .

不难构造出一个网络流模型 :

S -> 权值 , 权值 -> l_x , 权值 -> r_x , a_i = 0 的 i -> T. 这些边权值为 1

code :

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &x){
    static char ch; x = 0,ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
const int N = 500005;
struct Seg{
    #define lc o<<1
    #define rc o<<1|1
    int n,val[N],mn[N<<2],tag[N<<2];
    inline void up(int o){ mn[o] = min(mn[lc],mn[rc]); }
    inline void Build(int o,int l,int r){
        tag[o] = 0; if (l == r){ mn[o] = val[l]; return; }
        int mid = l+r>>1; Build(lc,l,mid); Build(rc,mid+1,r); up(o);
    }
    inline void Tag(int o,int v){ mn[o] += v,tag[o] += v; }
    inline void down(int o){ if (tag[o]) Tag(lc,tag[o]),Tag(rc,tag[o]),tag[o] = 0; }
    int ll,rr;
    inline void Add(int o,int l,int r){
        if (ll <= l && rr >= r){ Tag(o,-1); return; }
        down(o); int mid = l+r>>1; if (ll <= mid) Add(lc,l,mid); if (rr > mid) Add(rc,mid+1,r); up(o);
    }
    #undef lc
    #undef rc
    inline void init(){ Build(1,1,n); }
    inline void add(int l,int r){ ll = l,rr = r; if (ll <= rr) Add(1,1,n); } 
}T;
int n,a[N],lmx[N],rmn[N];
int cntid,cntc,cntz;
int pre0[N],id[N],pos[N],val[N],type[N];
inline void solve(){
    int i,x,ans,now;
    read(n);
    for (cntz = 0,i = 1; i <= n; ++i) read(a[i]),cntz += a[i]?0:1,pre0[i] = pre0[i-1] + (a[i]?0:1);
    for (i = 1; i <= n; ++i) lmx[i] = -1,rmn[i] = -1;
    for (i = 1; i <= n; ++i) type[i] = (pre0[i]-(a[i]?0:1) >= (cntz>>1)) ? 2 : 1; // 1 ... 1 2 .. 2
    for (i = 1; i <= n; ++i) if (a[i] && type[i] == 1) lmx[a[i]] = i;
    for (i = n; i >= 1; --i) if (a[i] && type[i] == 2) rmn[a[i]] = i;
    for (cntc = 0,i = 1; i <= n; ++i) if (lmx[i] != -1 || rmn[i] != -1) ++cntc;
    cntid = 0;
    for (i = 1; i <= n; ++i) if (type[i] == 2 && !a[i]) id[i] = ++cntid,pos[cntid] = i;
    T.n = cntid+1;
    for (i = 1; i <= cntid+1; ++i) T.val[i] = cntc + cntid + 1 - i;
    T.init();
    for (i = 1; i <= n; ++i) if (lmx[i] == -1 && rmn[i] != -1) x = rmn[i],T.add(1,pre0[x]+1-(cntz>>1));
    ans = min(cntz>>1,T.mn[1]);
    for (now = 0,i = 1; i <= n; ++i) if (type[i] == 1){
        if (!a[i]) ++now;
        if (a[i] && i == lmx[a[i]]){
            x = rmn[a[i]];
            if (x != -1) T.add(1,pre0[x]+1-(cntz>>1));
            else T.add(1,cntid+1);
        }
        ans = min(ans,T.mn[1]+now);
    }
    write(ans),putchar('\n');
}
int main(){ int T; read(T); while (T--) solve(); return 0; }