题解：AT_abc397_f [ABC397F] Variety Split Hard

· · 题解

首先这种给你一个序列让你求什么东西的问题肯定要先枚举一个什么东西，于是设当前枚举到了 now。

据此，我们可以设 f_i 表示 a_1\sim a_i 的不同元素个数加上 a_{i+1}\sim a_{now} 的不同元素个数，我们先来看看每次从 now-1 的状态到 now 的状态，f 有怎样的变化：

设 lst_i 表示上一个与 a_i 一样的元素的下标，没有则设为 0，则有 f_i=\sum\limits_{j=1}^i[lst_j=0]+\sum\limits_{j=i+1}^{now}[lst_j\le i]。前面的东西十分好处理，后面这个东西随着 now 的变化而变化，且我们发现每次枚举到 now 都会给满足 lst_{now} \le i <now 的 f_i 加一。

然后，我们只需要每次将答案与 \max(f_i,i<now)+g_{i+1} 取最大值即可，其中 g_i 表示 a_i\sim a_n 的不同元素个数。

于是我们发现需要对 f 进行以下操作：

采用线段树即可解决，时间复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define N 500005 
using namespace std;
int n,a[N],g[N],maxn[N*4],z[N*4],vis[N],lst[N],ans;
set<int>s;
void pushup(int x){
    maxn[x]=max(maxn[x*2],maxn[x*2+1]);
}
void pushdown(int x){
    if(z[x]){
        maxn[x*2]+=z[x];maxn[x*2+1]+=z[x];
        z[x*2]+=z[x];z[x*2+1]+=z[x];z[x]=0;
    }
}
void update(int x,int l,int r,int ql,int qr,int v){
    if(ql>qr)return;
    if(ql<=l&&r<=qr){
        maxn[x]+=v;z[x]+=v;return;
    }
    int mid=(l+r)>>1;pushdown(x);
    if(ql<=mid)update(x*2,l,mid,ql,qr,v);
    if(qr>mid)update(x*2+1,mid+1,r,ql,qr,v);
    pushup(x);
}
int query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return maxn[x];
    int mid=(l+r)>>1,ans=0;pushdown(x);
    if(ql<=mid)ans=max(ans,query(x*2,l,mid,ql,qr));
    if(qr>mid)ans=max(ans,query(x*2+1,mid+1,r,ql,qr));
    return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=n;i>=1;--i)s.insert(a[i]),g[i]=s.size();
    for(int i=1;i<=n;++i){
        lst[i]=vis[a[i]];
        vis[a[i]]=i;
    }
    int sum0=0;
    for(int i=1;i<n;++i){
        if(!lst[i])++sum0;
        update(1,1,n,i,i,sum0);update(1,1,n,max(lst[i],1),i-1,1);
    //  for(int j=1;j<=n;++j)cout<<query(1,1,n,j,j)<<" ";cout<<'\n';
        if(i!=1)ans=max(ans,query(1,1,n,1,i-1)+g[i+1]);
    }
    cout<<ans;
    return 0;
}