ABC-397-F - Variety Split Hard · znzryb
## 思路讲解
题意就是把一个序列三分，然后求最大种类数之和
参考题解
【AtCoder 初学者竞赛 397比赛讲解（ABC397）】 【精准空降到 30:17】 [https://www.bilibili.com/video/BV1eMQaYEEXa/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1817](https://www.bilibili.com/video/BV1eMQaYEEXa/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1817)
说实话，在看题解之前，我是不会想到这种方法的，毕竟就算枚举$i，j$也需要$O（n^2）$，加快验证过程也没有什么意义。
首先，我们有C题的经验，prei和sufj+1我们都知道
然后不能同时枚举i，j，我们不妨只枚举j（无所谓i，j）
这个怎么寻找突破口那？
容易发现，这个#[i+1,j]是否需要+1的起始位置就是aj+1上一次出现的位置，即$las_{a_{j+1}}$。
zkw线段树详细介绍（zkw线段树实现区间修改，区间查询最值）
想着用zkw线段树解决，但还是算了，就普通线段树吧。
然后一定要想清楚，按照我的编码方式j不需要现在加，因为包括在了las[j]。需要加的其实是A[j-1]，las[j-1]。
```cpp
FOR(j,3,N){
// 由于j是确定的，利用离线思想
// 线段树里存的相当于pre[i]+#[i+1,j-1]（j为目前的j）
if(las[A[j-1]]==0){
add(1,1,j-2,1);
}else{
add(1,las[A[j-1]],j-2,1); // 加到j-2就够了，j-1的时候该点以囊入pre
}
ans=max(ans,cntr[j]+query(1,1,j-2));
las[A[j-1]]=j-1;
// #ifdef LOCAL
// cerr<<j<<"\n";
// FOR(i,1,4*N){
// cerr<<i<<"--l:"<<tr[i].l<<" r:"<<tr[i].r<<" val:"<<tr[i].val<<"\n";
// }
// cerr<<"\n";
// #endif
}
cout<<ans<<"\n";
}
```
## AC代码
[https://atcoder.jp/contests/abc397/submissions/64623246](https://atcoder.jp/contests/abc397/submissions/64623246)
```cpp
// Problem: F - Variety Split Hard
// Contest: AtCoder - OMRON Corporation Programming Contest 2025 (AtCoder Beginner Contest 397)
// URL: https://atcoder.jp/contests/abc397/tasks/abc397_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3;
ll N,M,T,A[MAXN];
bool vis[MAXN];
bool visr[MAXN];
ll cnt[MAXN],cntr[MAXN];
struct TREE{
ll l=0,r=0,val=-INF;
}tr[MAXN*4];
ll lazy[MAXN*4];
inline ll ls(ll x){return x<<1;}
inline ll rs(ll x){return x<<1|1;}
inline void pushdown(ll node){
// 这句话还是重要的，防止RE
if(tr[node].l==tr[node].r) return;
if(lazy[node]!=0){
tr[ls(node)].val+=lazy[node];
tr[rs(node)].val+=lazy[node];
lazy[ls(node)]+=lazy[node];
lazy[rs(node)]+=lazy[node];
lazy[node]=0;
}
}
inline void pushup(ll node){
node/=2;
while(node){
tr[node].val=max(tr[ls(node)].val,tr[rs(node)].val);
node/=2;
}
}
void add(ll node,ll l,ll r,ll val){
if(r<l) return;
if(r<tr[node].l || l>tr[node].r){
return;
}
pushdown(node);
if(l<=tr[node].l && tr[node].r<=r){
lazy[node]+=val;
tr[node].val+=val;
pushup(node);
return;
}
ll mid=(tr[node].l+tr[node].r)/2;
// 只要不是和左节点一点关系都没有，我们都要进左节点
if((r<tr[node].l || l>mid)==false) add(ls(node),l,r,val);
if((r<mid+1 || l>tr[node].r)==false) add(rs(node),l,r,val);
}
void build(ll node,ll l,ll r){
if(l>r){
return;
}
if(l==r){
tr[node].l=l;
tr[node].r=r;
tr[node].val=0; // 用来使用
return;
}
tr[node].l=l;
tr[node].r=r;
ll mid=l+r>>1;
build(ls(node),l,mid);
build(rs(node),mid+1,r);
}
ll query(ll node,ll l,ll r){
if(r<tr[node].l || l>tr[node].r){
return -INF;
}
pushdown(node);
if(l<=tr[node].l && tr[node].r<=r){
return tr[node].val;
}
ll mid=(tr[node].l+tr[node].r)/2;
ll res=-INF;
// 只要不是和左节点一点关系都没有，我们都要进左节点
if((r<tr[node].l || l>mid)==false) res=max(res,query(ls(node),l,r));
if((r<mid+1 || l>tr[node].r)==false) res=max(res,query(rs(node),l,r));
return res;
}
ll las[MAXN];
inline void solve(){
cin>>N;
for(int i=1;i<=N;++i){
cin>>A[i];
}
FOR(i,1,N){
if(!vis[A[i]]) cnt[i]=cnt[i-1]+1;
else cnt[i]=cnt[i-1];
vis[A[i]]=true;
}
ROF(i,N,1){
if(!visr[A[i]]) cntr[i]=cntr[i+1]+1;
else cntr[i]=cntr[i+1];
visr[A[i]]=true;
}
build(1,1,N);
FOR(i,1,N){
// 初始化线段树
add(1,i,i,cnt[i]);
}
// #ifdef LOCAL
// FOR(i,1,N){
// cerr<<cnt[i]<<" ";
// }
// cerr<<"\n";
// #endif
ll ans=0;
// 在该j下的最好情况是suf[j]+max(pre[i]+#[i+1,j-1])
// #[i+1,j-1]是指该闭区间内的数字种数
las[A[1]]=1; // 该值最后一次出现的位置
// las[A[2]]=2;
FOR(j,3,N){
// 由于j是确定的，利用离线思想
// 线段树里存的相当于pre[i]+#[i+1,j-1]（j为目前的j）
if(las[A[j-1]]==0){
add(1,1,j-2,1);
}else{
add(1,las[A[j-1]],j-2,1); // 加到j-2就够了，j-1的时候该点以囊入pre
}
ans=max(ans,cntr[j]+query(1,1,j-2));
las[A[j-1]]=j-1;
// #ifdef LOCAL
// cerr<<j<<"\n";
// FOR(i,1,4*N){
// cerr<<i<<"--l:"<<tr[i].l<<" r:"<<tr[i].r<<" val:"<<tr[i].val<<"\n";
// }
// cerr<<"\n";
// #endif
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>T;
// while(T--){
// solve();
// }
solve();
return 0;
}
/*
AC
https://atcoder.jp/contests/abc397/submissions/64623246
10
1 2 3 3 4 5 6 6 7 8
10
*/
```
## 心路历程（WA，TLE，MLE……）
RE是因为没加这句话
```cpp
inline void pushdown(ll node){
// 这句话还是重要的，防止RE
if(tr[node].l==tr[node].r) return;
if(lazy[node]!=0){
tr[ls(node)].val+=lazy[node];
tr[rs(node)].val+=lazy[node];
lazy[ls(node)]+=lazy[node];
lazy[rs(node)]+=lazy[node];
lazy[node]=0;
}
}
```