题解：AT_abc397_f Variety Split Hard

· · 题解

题意：

将数组分割成三个非空连续子数组，使得三个子数组中不同元素的数量之和最大。

思路：

线段树。

可以先把线段树的加法模版做了再来看。

定义数组 pre，其中 pre_i 表示前 i 个元素中不同元素的数量。
定义数组 suf，其中 suf_i 表示从位置 i 到末尾的不同元素数量。

这样就可以差不多可以把这道题的弱化版，本场的 C 题写出来。

接下来继续考虑本题。

定义 mid(i,j) 是对于 A 数组中的所有满足下标 i \le k \le j 的 A_k 的不同元素个数。
用数学方式可以表示为 mid(i, j)= \left| \{ A_k \mid i \leq k \leq j \} \right|。

对于每个分割点 j（第二个分割点的位置），我们需要找到最优的第一个分割点 i，使得 pre_i+mid(i+1,j)+suf_{j+1} 的值最大。

我们可以使用线段树维护每个位置 i 的 pre_i+mid(i+1,j) 的最大值。

在维护中间段时，当 A_j 出现重复时，只有 i \ge l 的分割点会使中间段包含新的 A_j，因此要让区间 [l,j−1] 维护的值加一。

定义一个变量 maxx 用来存答案。

对每个 j，查询线段树维护的区间 [1,j−1] 的值，加上 suf_{j+1} 后更新全局最大值。

总时间复杂度 O(N \log N)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
const int N=3e5+5;
int n,a[N*4],pre[N*4],suf[N*4],las[N*4];
vector<int>value(N*4),lazy(N*4);
void build(int now,int l,int r){
    if(l==r){
        value[now]=pre[l];
        return;// 别忘了 return 赛时 15 分钟打忘记加喜提 RE
    }
    int mid=l+(r-l)/2;
    build(2*now,l,mid);
    build(2*now+1,mid+1,r);
    value[now]=max(value[now*2],value[now*2+1]);
}
void push(int now){// 懒标记
    if(lazy[now]==0)return;
    value[2*now]+=lazy[now];
    value[2*now+1]+=lazy[now];
    lazy[2*now]+=lazy[now];
    lazy[2*now+1]+=lazy[now];
    lazy[now]=0;
}
void change(int now,int l,int r,int ql,int qr,int val){
    if(qr<l||ql>r)return;
    if(ql<=l&&r<=qr){
        value[now]+=val;
        lazy[now]+=val;
        return;
    }
    push(now);
    int mid=l+(r-l)/2;
    change(2*now,l,mid,ql,qr,val);
    change(2*now+1,mid+1,r,ql,qr,val);
    value[now]=max(value[2*now],value[now*2+1]);
}
int ans(int now,int l,int r,int ql,int qr){
    if(qr<l||ql>r)return 0;
    if(ql<=l&&r<=qr){
        return value[now];
    }
    push(now);
    int mid=l+(r-l)/2;
    return max(ans(now*2,l,mid,ql,qr),ans(now*2+1,mid+1,r,ql,qr));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    unordered_set<int>spre;
    pre[0]=0;
    for(int i=1;i<=n;i++){// 处理前 i 个元素中不同元素的数量
        spre.insert(a[i]);
        pre[i]=spre.size();
    }
    unordered_set<int>ssuf;
    suf[n+1]=0;
    for(int i=n;i>=1;i--){// 处理从位置 i 到末尾的不同元素数量。
        ssuf.insert(a[i]);
        suf[i]=ssuf.size();
    }
    build(1,1,n-1);// 建树
    int maxx=0;
    for(int j=1;j<=n-1;j++){
        int x=a[j];
        int l=las[x];
        int le=max(l,1);
        int r=j-1;
        if(l<=r){
            change(1,1,n-1,le,r,1);
        }
        las[x]=j;
        if(j>=2){
            int cm=ans(1,1,n-1,1,j-1);
            int cs=cm+suf[j+1];
            maxx=max(maxx,cs);
        }
    }
    cout<<maxx;
    return 0;
}

提交记录。