Znzryb's Blog
0%

ABC-397-F - Variety Split Hard 

Posted on Edited on

思路讲解

题意就是把一个序列三分，然后求最大种类数之和

image

参考题解

【AtCoder 初学者竞赛 397比赛讲解（ABC397）】 【精准空降到 30:17】 https://www.bilibili.com/video/BV1eMQaYEEXa/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1817

说实话，在看题解之前，我是不会想到这种方法的，毕竟就算枚举i，ji，j也需要O（n2）O（n^2），加快验证过程也没有什么意义。

首先，我们有C题的经验，prei和sufj+1我们都知道

image

然后不能同时枚举i，j，我们不妨只枚举j（无所谓i，j）

image

这个怎么寻找突破口那？

image

容易发现，这个#[i+1,j]是否需要+1的起始位置就是aj+1上一次出现的位置，即lasaj+1las_{a_{j+1}}。

zkw线段树详细介绍（zkw线段树实现区间修改，区间查询最值）

想着用zkw线段树解决，但还是算了，就普通线段树吧。

然后一定要想清楚，按照我的编码方式j不需要现在加，因为包括在了las[j]。需要加的其实是A[j-1]，las[j-1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
// 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是因为没加这句话

1
2
3
4
5
6
7
8
9
10
11
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;
	}
}