{% link 洛谷文章链接,xyx404,https://www.luogu.com.cn/article/d7uchu06 %}
题意： #
将数组分割成三个非空连续子数组，使得三个子数组中不同元素的数量之和最大。
思路： #
线段树。
可以先把线段树的加法模版做了在来看。
定义数组 $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;
}
提交记录。