题解：CF1969E Unique Array

· · 题解

Description

定义一个子段是独特子段，当且仅当存在一个整数在这个子段中出现恰好一次。

给定序列 a，求至少替换多少个元素，才能使得 a 的所有子段为独特子段。

Solution

考虑扫描线，定义一个二维平面，横轴代表左端点，纵轴代表右端点，点 (l,r) 代表子段 [l,r]。

依次考虑每一个点，设 pre_i 为 a_i 前面第一个与其相同的数，suf_i 为 a_i 后面第一个与其相同的数。

则对于所有 l \in [pre_i+1,i]，r \in [i,suf_i-1]，[l,r] 为独特子段，这在二维平面上可以转化为一个矩形，可以用扫描线维护矩形面积并，这样未被矩形覆盖的点就不是独特子段。

我们从右到左扫描线，设当前扫描到左端点 x，若有对应右端点未被覆盖。此时有结论，直接将 a_x 替换为序列中未出现过的数一定是最优的。

感性证明一下，将 a_x 替换后，对于所有 l \in [1,x]，r \in [x,n]，[l,r] 都为独特子段。

由于是从右到左的扫描线，当扫描到 x 时，所有左端点 > x 的子段都被处理完成了，因此我们只关心修改后左端点 \le x 的子段，即扫描线左侧的影响。而修改 x 所影响的矩形可以完全覆盖修改其他点的矩形，从而得证。

Code

#include <bits/stdc++.h>
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=3e5+5;
struct node{
    int l,r,k;
};
int T,n,a[N],b[N],pr[N],sf[N],ans;
int mi[N<<2],tag[N<<2];
vector<node>e[N];
int read(){
    int k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        k=k*10+ch-'0',ch=getchar();
    return k;
}
void pushup(int k){
    mi[k]=min(mi[ls],mi[rs]);
}
void pushdown(int k){
    if(tag[k]){
        mi[ls]+=tag[k],tag[ls]+=tag[k];
        mi[rs]+=tag[k],tag[rs]+=tag[k];
        tag[k]=0;
    }
}
void build(int k,int l,int r){
    tag[k]=0;
    if(l==r){
        mi[k]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(k);
}
void modify(int k,int l,int r,int x,int y,int v){
    if(x>y) return;
    if(x<=l&&r<=y){
        mi[k]+=v,tag[k]+=v;
        return;
    }
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls,l,mid,x,y,v);
    if(mid+1<=y) modify(rs,mid+1,r,x,y,v);
    pushup(k);
}
int main(){
    T=read();
    while(T--){
        ans=0;
        n=read();
        for(int i=1;i<=n;i++)
            a[i]=read();
        for(int i=1;i<=n;i++){
            pr[i]=b[a[i]];
            b[a[i]]=i;
        }
        for(int i=1;i<=n;i++) b[i]=n+1;
        for(int i=n;i>=1;i--){
            sf[i]=b[a[i]];
            b[a[i]]=i;
        }
        for(int i=1;i<=n;i++) b[i]=0;
        for(int i=1;i<=n;i++){
            e[pr[i]].push_back((node){i,sf[i]-1,-1});
            e[i].push_back((node){i,sf[i]-1,1});
        }
        build(1,1,n);
        for(int i=n;i>=1;i--){
            for(node j:e[i])
                modify(1,1,n,j.l,j.r,j.k);
            modify(1,1,n,1,i-1,1);
            if(mi[1]==0){
                modify(1,1,n,i,n,1);
                ans++;
            }
            modify(1,1,n,1,i-1,-1);
        }
        printf("%d\n",ans);
        for(int i=0;i<=n;i++)
            e[i].clear();
    }
    return 0;
}