AT_abc397_f [ABC397F] Variety Split Hard

AT_abc397_f [ABC397F] Variety Split Hard

洛谷题目传送门

题目描述

本题是 C 题的强化版，分割个数变为 $3$ 个。

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots ,A_N)$。

当在 $A$ 的两个位置将其分割为 $3$ 个非空的连续子序列时，求这三个子序列中不同整数的种类数之和的最大可能值。

更严格地说，对于满足 $1\le i<j\le N-1$ 的整数对 $(i,j)$，分别计算子序列 $(A_1,A_2,\dots ,A_i)$、$(A_{i+1},A_{i+2},\dots ,A_j)$ 和 $(A_{j+1},A_{j+2},\dots ,A_N)$ 中不同整数的种类数之和，并求这些和的最大值。

输入格式

输入通过标准输入给出，格式如下：

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

5
3 1 4 1 5

输出 #1

5

输入输出样例 #2

输入 #2

10
2 5 6 4 4 1 1 3 1 4

输出 #2

9

说明/提示

约束条件

• $3\le N\le 3\times 10^5$
• $1\le A_i\le N$ ($1\le i\le N$)
• 输入均为整数

样例解释 1

当 $(i,j)=(2,4)$ 时，分割为 $(3,1)$、$(4,1)$ 和 $(5)$ 这三个连续子序列，各自的种类数分别为 $2,2,1$，和为 $5$。由于无法得到比 $5$ 更大的值，因此答案是 $5$。其他如 $(i,j)=(1,3)$、$(2,3)$、$(3,4)$ 等情况也能得到和为 $5$。

思路详解

这道题是c题的强化版本，他由c题的只分为2段变为了分为3段。再使用c题的方法枚举是显然会超时的，所以我们需要一种更高效的方法。

首先我们肯定还要枚举第一个断点$i$，考虑对于每一个$i$，第二个断点$j$取在何处最优？？？

我们先考虑每个数的贡献值：

1. 假如一个数$x$只在区间$[i+1,n]$出现了一次，那他对于这一段区间的贡献都是1，因为他无论取在$j$左右都只记作一个数。
2. 假如数$x$出现了多次，那对于区间$[fst,lst)$($fst$为最早出现的位置，$lst$为最晚出现的位置，取不到是因为$j$为第2块的右边界)他有2的贡献，对其余区域和情况1一样，只有1的贡献。

显然，累计的贡献值最大的位置即为最优的$j$。

那我们该如何实现呢？我们想到用一个数组维护贡献值。但是我们发现，只要出现了一个数字，他对他左边都一定有1的贡献，那我们完全不需要管贡献为1的，使用一个变量$js$记录一下有多少个数字即可。

而且，我们可以发现1的贡献是往左边的，那我们肯定要从右往左枚举第一个断点$i$，在计算之后加入新的节点。

考虑如何处理2的贡献。由于我们已经加过1了，那只需要将区间$[fst,lst-1]$加1即可。由于对于同一个数字，我们之前可能已经加过一部分了，我们每次只需要对两个相邻的同数字之间加上1即可，即将区间$[i+1,pr{e}_{a[i]}-1]$($pr{e}_{a[i]}$为上一次$a[i]$出现的位置)加1即可。

最后的答案即位$max(前i个的数量+js+ma{x}_{val}(i+1,n-1))$($ma{x}_{val}$为最大贡献)。

很明显，我们既要区间加，又要区间求最大值，那我们直接使用线段树/平衡树即可，这里我使用平衡树。

code

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,a[N];
struct lit{
	int val,siz,add,mx;
	int pri;
	lit *l,*r;
	lit(int v){
		val=mx=v;siz=1;add=0;
		pri=rand();
		l=r=nullptr;
	}
};
class FHQ{//FHQ模板
private:
	lit *root;
	int getsize(lit *u){return u?u->siz:0;}
	int getmax(lit *u){return u?u->mx:-0x3f3f3f3f;}
	void pushup(lit *&u){
		if(!u)return;
		u->siz=1+getsize(u->l)+getsize(u->r);
		u->mx=max(getmax(u->l),max(getmax(u->r),u->val));
	}
	void mark_co(lit *&u,int v){
		if(!u)return;
		u->add+=v;
		u->mx+=v;
		u->val+=v;
	}
	void pushdown(lit *&u){
		if(!u||!u->add)return;
		mark_co(u->l,u->add);
		mark_co(u->r,u->add);
		u->add=0;
	}
	void split(lit *u,int k,lit *&x,lit *&y){
		if(!u){x=y=nullptr;return;}
		pushdown(u);
		int ls=getsize(u->l);
		if(ls+1<=k){x=u;split(u->r,k-ls-1,x->r,y);pushup(x);}
		else{y=u;split(u->l,k,x,y->l);pushup(y);}
	}
	lit *merge(lit *x,lit *y){
		if(!x)return y;
		if(!y)return x;
		pushdown(x);pushdown(y);
		if(x->pri>y->pri){x->r=merge(x->r,y);pushup(x);return x;}
		else{y->l=merge(x,y->l);pushup(y);return y;}
	}
	void _print(lit *u){
		if(!u)return ;
		pushdown(u);
		_print(u->l);cout<<u->val<<' ';_print(u->r);
	}
public:
	void print(){
		_print(root);cout<<'\n';
	}
	void push_back(int v){//往后插入一个数
		root=merge(root,new lit(v));
	}
	void change_add(int le,int ri,int v){//区间加
		lit *l,*mid,*r;
		split(root,ri,mid,r);
		split(mid,le-1,l,mid);
		mark_co(mid,v);
		root=merge(merge(l,mid),r);
	}
	int query_max(int le,int ri){//区间求最值
		lit *l,*mid,*r;
		split(root,ri,mid,r);
		split(mid,le-1,l,mid);
		int res=getmax(mid);
		root=merge(merge(l,mid),r);
		return res;
	}
}tr;
int vis[N],cnt[N];
//cnt[i]表示前i个的数量
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)tr.push_back(0);
	memset(vis,0,sizeof(vis));
	int ans=0;
//枚举第一组终点i，考虑每个数字对后面的贡献
//若一个数字只出现一次，那他对所有位置都有1的贡献
//若一个数字出现了多次，那对于每一个相邻的当前的数字，他对中间的位置都有2贡献，对其他只有1贡献
//但是要注意第一次出现时已经加过1，则后来只需加1
	for(int i=1;i<=n;i++){//预处理出前i个的数量
		if(!vis[a[i]]){
			vis[a[i]]=1;cnt[i]=1;
		}
		cnt[i]+=cnt[i-1];
	}
	memset(vis,0,sizeof(vis));
	int js=0;
	for(int i=n;i>=1;i--){
//由于要分为3组，所以要预留2个位置
		if(i<=n-2)ans=max(ans,js+cnt[i]+tr.query_max(i+1,n-1));
		if(!vis[a[i]])vis[a[i]]=i,js++;//之前没有出现过，js++
		else{
			tr.change_add(i,vis[a[i]]-1,1);//将对应区间加上1
			vis[a[i]]=i;//vis记录上一次出现位置
		}
	}
	cout<<ans;
	return 0;
	
}