题解：CF1969E Unique Array

· · 题解

题意：定义一个数组 a_1,a_2,\cdots,a_n 是合法的当且仅当对于所有子区间 [l,r]，都存在一个数 x，满足 x 在 a_l,a_{l+1},\cdots,a_r 中只出现一次，给定一个数组，求至少替换多少个元素，才可以使数组合法。

首先，一个显然的策略，设把 a_x 替换成 y，则 y 两两不同且不在原数组中出现，此时，对于 l\in[1,x],r\in[x,n] 的所有子区间都会合法，相当于把原数组从 x 下标处断开。

所以，题意可以理解为，至少分成多少段，使得每段均合法（段与段之间有 1 的空隙）。

此时，有一个显然的贪心，从头扫到尾，若扫到一个前缀不合法，就把这个前缀断开，去掉结尾，分成一段。

证明也是显然的，首先，不可能延后断开位置，这样会使其不合法，若提前了断开的位置，相当于给后面的前缀前面插入若干数，这样不会新前缀的断开位置变优。

然后，我们考虑如何判断一段前缀是否合法。

注意到，若扫到了 [pre,r]，且 [pre,r-1] 时均未断开，则只需判断满足 l\in[pre,r] 的 [l,r] 的合法情况，用一个数据结构维护每个 l 是否合法（即 [l,r] 中只出现一次的数的个数），若加入一个数 x，前面一个 x 在位置 t1_x，前面倒数第二个 x 在位置 t2_x，则可以区间 (t2_x,t1_x] 减 1，区间 (t1_x,r] 加 1，查询是否合法也只需查询区间 [pre,r] 最小值，如果为 0 则不合法，令 pre 赋值为 r+1，答案 +1 即可。

数据结构就用一个区间加，求区间 \min 的线段树就行。

代码：

#include<bits/stdc++.h>
using namespace std;
struct segment_tree
{
    int l,r,lazy,minn;
}a[1200005];
int b[300005];
const int inf=0x3f3f3f3f;
void build(int pos,int l,int r)
{
    a[pos]={l,r,0,0};
    if(l==r)
        return;
    int mid=l+r>>1;
    build(2*pos,l,mid);
    build(2*pos+1,mid+1,r);
}
void update(int pos)
{
    a[pos].minn=min(a[2*pos].minn,a[2*pos+1].minn);
}
void putlazy(int pos,int x)
{
    a[pos].lazy+=x;
    a[pos].minn+=x;
}
void pushdown(int pos)
{
    putlazy(2*pos,a[pos].lazy);
    putlazy(2*pos+1,a[pos].lazy);
    a[pos].lazy=0;
}
void add(int pos,int l,int r,int x)
{
    if(r<a[pos].l||l>a[pos].r||l>r)
        return;
    if(l<=a[pos].l&&r>=a[pos].r)
    {
        putlazy(pos,x);
        return;
    }
    pushdown(pos);
    add(2*pos,l,r,x);
    add(2*pos+1,l,r,x);
    update(pos);
}
int getmin(int pos,int l,int r)
{
    if(r<a[pos].l||l>a[pos].r)
        return inf;
    if(l<=a[pos].l&&r>=a[pos].r)
        return a[pos].minn;
    pushdown(pos);
    return min(getmin(2*pos,l,r),getmin(2*pos+1,l,r));
}
int t1[300005],t2[300005];
void test()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=1;i<=n;i++)
        t1[i]=t2[i]=0;
    build(1,1,n);
    int pre=1,cnt=0;
    for(int i=1;i<=n;i++)
    {
        add(1,t2[b[i]]+1,t1[b[i]],-1);
        add(1,t1[b[i]]+1,i,1);
        t2[b[i]]=t1[b[i]];
        t1[b[i]]=i;
        if(getmin(1,pre,i)==0)
        {
//          cout<<i<<" ";
            cnt++;
            pre=i+1;
        }
    }
    cout<<cnt<<"\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
        test(); 
}