题解：AT_abc397_f Variety Split Hard

xyx4042025-03-152025-03-15

引用站外地址，不保证站点的可用性和安全性

洛谷文章链接

xyx404

题意：

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

思路：

线段树。

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

定义数组 $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;
}

提交记录。