Znzryb's Blog

CF-1027-E. Kirei Attacks the Estate

Posted on 2025-06-07 Edited on 2026-02-17

思路讲解

是比较简单的树上dp问题，记录一下。

void dfs(ll node,ll x0,ll x1,ll cnt){
	// x0表示cnt%2==0时加
	if(vis[node]) return;
	vis[node]=true;
	ans[node]= cnt%2==0?A[node]+x1:A[node]+x0;
	if(cnt%2==0){
		x0-=A[node];
		x1+=A[node];
	}
	if(cnt%2==1){
		x0+=A[node];
		x1-=A[node];
	}
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i];
		if(vis[lnode]) continue;
		dfs(lnode,max(0ll,x0),max(0ll,x1),cnt+1);
	}
}

AC代码

https://codeforces.com/contest/2114/submission/323228554

源代码

// Problem: E. Kirei Attacks the Estate
// Contest: Codeforces - Codeforces Round 1027 (Div. 3)
// URL: https://codeforces.com/contest/2114/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.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())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
vector<ll> g[MAXN];		// 记得要清空
bool vis[MAXN];
ll ans[MAXN];
ll mxx[2];
inline void init(){
	mxx[0]=0;mxx[1]=0;
	FOR(i,0,N+5){g[i].clear();vis[i]=false;}
}
//                         cnt 是指 node 是该 vertical path 上的第几个点
void dfs(ll node,ll x0,ll x1,ll cnt){
	// x0表示cnt%2==0时加
	if(vis[node]) return;
	vis[node]=true;
	ans[node]= cnt%2==0?A[node]+x1:A[node]+x0;
#ifdef LOCAL
    debug(node);
    debug(ans[node]);
    debug(x0);
    debug(x1);
    debug(A[node]);
#endif
	if(cnt%2==0){
		x0-=A[node];
		x1+=A[node];
	}
	if(cnt%2==1){
		x0+=A[node];
		x1-=A[node];
	}
#ifdef LOCAL
    debug(x0);
    debug(x1);
    cerr<<"\n";
#endif
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i];
		if(vis[lnode]) continue;
		dfs(lnode,max(0ll,x0),max(0ll,x1),cnt+1);
	}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){cin>>A[i];}
	FOR(i,1,N-1){
		ll u,v;cin>>u>>v;
		g[u].pb(v);g[v].pb(u);
	}
	// root=1;
	dfs(1,0,0,1);
	FOR(i,1,N){cout<<ans[i]<<" ";}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2114/submission/323228554
*/

心路历程（WA，TLE，MLE……）

Edu-179-E. Changing the String

Posted on 2025-06-04 Edited on 2026-02-17

思路讲解

感觉每次选择都可能有后效性怎么办？

1
2
3

// 碰到b,a   c,a operate 在最近的位置
// a,b  a,c   not operate
// b,c   c,b    operate or not?

仔细一想那，这道题目也没有那么复杂其实，其实只有b，c是需要考虑是否操作的。

只考虑那么一种情况的话，其实就看后面有没有c，a，而且b的前面c的数量啦。

https://www.cnblogs.com/fwdzh/p/18909502

这个题解告诉我们，我们是不可能在线处理的，这个难度是比较大的，但是我前面一直在想这个（QAQ）。

AC代码

https://codeforces.com/contest/2111/submission/322930903

源代码

// Problem: E. Changing the String
// Contest: Codeforces - Educational Codeforces Round 179 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2111/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.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())
#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 getFro(vec) (vec.empty()?0:vec.front())
// #define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
// #define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
// variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
// #define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
// var.end())-var.begin());} while (0)
// #define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
// std::cerr<<"\n"; }while(0)
// #define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
// & pair : variable) \
// { std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
// std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
// #define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
using arc2=array<char,2>;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(1e9)+9;	// 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
/*

*/
// arc2 opC[MAXN];
set<ll> g[50];	// 直接懒得上有序表了，直接用vector 吧 开摆
inline void solve(){
	cin>>N>>Q;
	FOR(i, 0, 50-1) g[i].clear();
	// g[0].clear();g[1].clear();g[2].clear();
	// set<arc2> opC;
	string s;
	cin>>s;
	// FOR(i,0,SZ(s)-1){
		// g[s[i]-'a'].pb(i);
	// }
	FOR(i,1,Q){
		char x,y;
		cin>>x>>y;
		g[(x-'a')*5+y-'a'].insert(i);
	}
	// 碰到b,a   c,a operate 在最近的位置
	// a,b  a,c   not operate
	// b,c   c,b    operate or not?
	FOR(i,0,N-1){		
		if(s[i]=='a'){
			continue;
		}
		// 2 'c' -> 'a'  'c'->'b'->'a'  'c'->'b'
		if(s[i]=='c'){
			char x='c',y='a';
			ll idx=(x-'a')*5+y-'a';
			if(!g[idx].empty()){
				// g[idx].pop_front();		// 后面的操作是需要b->c->a组合，所以尽量删前面的
				g[idx].erase(g[idx].begin());
				s[i]='a';
			}else{
				ll idx2=('c'-'a')*5+'b'-'a',idx3=('b'-'a')*5;
				if(g[idx2].empty()) continue;
				if(g[idx3].empty()){
					// g[idx2].pop_back();
					g[idx2].erase(prev(g[idx2].end()));
					s[i]='b';
				}else{
					if(*g[idx2].begin()<*g[idx3].rbegin()){
						// g[idx2].pop_front();
						auto it=g[idx3].lower_bound(*g[idx2].begin());
						g[idx2].erase(g[idx2].begin());
						g[idx3].erase(it);
						s[i]='a';
					}else{
						// g[idx2].pop_back();
						// s[i]='b';
						g[idx2].erase(g[idx2].begin());
						s[i]='b';
					}
				}
			}
		}else{		// 1'b'->'a' 'b'->'c'->'a'
			char x='b',y='a';
			ll idx=(x-'a')*5+y-'a';
			// if(!g[idx].empty()){
				// g[idx].pop_front(); // 后面的操作是需要'c'->'b'->'a'组合，所以尽量删前面的
				// s[i]='a';
			// }else{
				// ll idx2=('b'-'a')*5+'c'-'a',idx3=('c'-'a')*5;
				// if(g[idx2].empty()) continue;
				// if(g[idx3].empty()){
					// // g[idx2].pop_back();
					// // s[i]='b';
				// }else{
					// if(g[idx2].front()<g[idx3].back()){
						// g[idx2].pop_front();
						// g[idx3].pop_back();
						// s[i]='a';
					// }else{
// 						
					// }
				// }
			// }
			if(!g[idx].empty()){
				// g[idx].pop_front(); // 后面的操作是需要'c'->'b'->'a'组合，所以尽量删前面的
				g[idx].erase(g[idx].begin());
				s[i]='a';
			}else{
				ll idx2=('b'-'a')*5+'c'-'a',idx3=('c'-'a')*5;
				if(g[idx2].empty()) continue;
				if(g[idx3].empty()){
					// g[idx2].pop_back();
					g[idx2].erase(prev(g[idx2].end()));
					s[i]='b';
				}else{
					if(*g[idx2].begin()<*g[idx3].rbegin()){
						// g[idx2].pop_front();
						auto it=g[idx3].lower_bound(*g[idx2].begin());
						g[idx2].erase(g[idx2].begin());
						g[idx3].erase(it);
						s[i]='a';
					}
				}
			}
		}
	}
	cout<<s<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2111/submission/322930903
*/

心路历程（WA，TLE，MLE……）

那么我们发现，匹配应该是这样匹配，而不是用最大的匹配最小的。

if(*g[idx2].begin()<*g[idx3].rbegin()){
	// g[idx2].pop_front();
	auto it=g[idx3].lower_bound(*g[idx2].begin());
	g[idx2].erase(g[idx2].begin());
	g[idx3].erase(it);
	s[i]='a';
}

Edu-179-D. Creating a Schedule

Posted on 2025-06-04 Edited on 2026-02-17

思路讲解

这道D题确实不算太难，我赛时应该也是可以写出来的。

采用类似于下图的构造方式即可

AC代码

https://codeforces.com/contest/2111/submission/322856069

源代码

// Problem: D. Creating a Schedule  D. 创建时间表
// Contest: Codeforces - Educational Codeforces Round 179 (Rated for Div. 2)教育 Codeforces 第 179 轮（评级为 Div. 2）
// URL: https://codeforces.com/contest/2111/problem/D
// Memory Limit: 512 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.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())
#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 getFro(vec) (vec.empty()?0:vec.front())
// #define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
// #define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
// variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
// #define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
// var.end())-var.begin());} while (0)
// #define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
// std::cerr<<"\n"; }while(0)
// #define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
// & pair : variable) \
// { std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
// std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
// #define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9;	// 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
// ll ans[MAXN][MAXN];
/*

*/

inline void solve(){
	scanf("%lld%lld",&N,&M);
	FOR(i,1,M){
		ll num;
		scanf("%lld",&A[i]);
		// A[i]=num/100;
	}
	sort(A+1,A+1+M);
	ll beg=0,ed=M+1;
	FOR(i,1,N){
		if(i%2==1){
			++beg;--ed;
			FOR(j,1,6){
				if(j%2==1) printf("%lld ",A[beg]);
				else printf("%lld ",A[ed]);
			}
			printf("\n");
		}else{
			FOR(j,1,6){
				if(j%2==1) printf("%lld ",A[ed]);
				else printf("%lld ",A[beg]);
			}
			printf("\n");
		}
		
	}
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	scanf("%lld",&lT);
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2111/submission/322856069
*/

心路历程（WA，TLE，MLE……）

CF-1028-D. Gellyfish and Camellia Japonica（直接构造等于难，构造最小的大于等于）

Posted on 2025-06-02 Edited on 2026-02-17

思路讲解

https://www.luogu.com.cn/article/rae0b6wl

总体思路就是将等于目标转变为构造最小的大于等于目标的构造

ROF(i,Q,1){
	ll x=Op[i][0],y=Op[i][1],z=Op[i][2];
	C[x]=max(C[x],C[z]);
	C[y]=max(C[y],C[z]);
	if(x!=z && y!=z) C[z]=0; 
}

既然是要被覆盖的，我们还要构造最小的吗，所以我们令

AC代码

https://codeforces.com/contest/2115/submission/323143930

源代码

// Problem: B. Gellyfish and Camellia JaponicaB. 水母和山茶花
// Contest: Codeforces - Codeforces Round 1028 (Div. 1)Codeforces 第 1028 轮（第 1 组）
// URL: https://codeforces.com/contest/2115/problem/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.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())
#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 debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)


using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(1e9)+9;	// 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],B[MAXN],C[MAXN];
/*

*/
arr3 Op[MAXN];
inline void solve(){
	cin>>N>>Q;
	FOR(i,1,N){
		cin>>B[i];
		C[i]=B[i];
	}
	FOR(i,1,Q){ll x,y,z;cin>>x>>y>>z;Op[i]={x,y,z};}
	// 总体思路就是将等于目标转变为构造最小的 大于等于目标的构造
	ROF(i,Q,1){
		ll x=Op[i][0],y=Op[i][1],z=Op[i][2];
		C[x]=max(C[x],C[z]);
		C[y]=max(C[y],C[z]);
		if(x!=z && y!=z) C[z]=0; 
	}
	FOR(i,1,N) A[i]=C[i];
	FOR(i,1,Q){
		ll x=Op[i][0],y=Op[i][1],z=Op[i][2];
		C[z]=min(C[x],C[y]);
	}
	FOR(i,1,N){
		if(C[i]!=B[i]){
			cout<<-1<<"\n";
			return;
		}
	}
	FOR(i,1,N){
		cout<<A[i]<<' ';
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2115/submission/323143930
*/

心路历程（WA，TLE，MLE……）

https://codeforces.com/contest/2115/submission/322643402

比最大条件小的点是不被允许的，那么填什么最好呢？

https://codeforces.com/contest/2115/submission/322665243

1
10 10
4 3 8 4 2 4 4 4 4 2 
9 6 8
7 1 4
2 5 5
8 1 8
7 4 6
9 7 8
6 8 8
8 4 5
9 10 5
3 1 9

附随机数据生成器

源代码

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.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())
#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 getFro(vec) (vec.empty()?0:vec.front())
// #define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
// #define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
// variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
// #define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
// var.end())-var.begin());} while (0)
// #define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
// std::cerr<<"\n"; }while(0)
// #define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
// & pair : variable) \
// { std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
// std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
// #define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9;	// 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],B[MAXN];
/*

*/
arr3 xyz[MAXN];
inline void solve(){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	N=10,Q=10;
	uniform_int_distribution<> dist(1,N),dist2(1,N);
	printf("1\n");
	printf("%lld %lld\n",N,Q);
	FOR(i,1,N){
		A[i]=dist(rng);
	}
	FOR(i,1,Q){
		ll x=dist2(rng),y=dist2(rng),z=dist2(rng);
		A[z]=min(A[x],A[y]);
		xyz[i]={x,y,z};
	}
	FOR(i,1,N){
		printf("%lld ",A[i]);
	}
	printf("\n");
	FOR(i,1,Q){
		int x=xyz[i][0],y=xyz[i][1],z=xyz[i][2];
		printf("%d %d %d\n",x,y,z);
	}
	
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	// scanf("%lld",&lT);
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/

https://www.cnblogs.com/cjcf/p/18906536

给出最后的结果和操作步骤，求初始数组

通过贪心，我们发现在A[x]有多条边的时候，只能选择满足最大的边（条件，边权为A[z]大小）

比最大条件小的点是不被允许的，那么我们就要看是就选这个最大条件还是选自己的值（如果自己的值比最大条件大）。

贪心的来说，如果自己的值是要被覆盖的，那么肯定选条件值，如果不被覆盖，那肯定就选自己的值。

当然，上面的这些只针对于不是多重覆盖的情况，如果出现多重覆盖情况，那么只保留最后覆盖情况（前面覆盖了也是白覆盖）。

那么我们发现，我们小瞧了这道题目，就是说操作之间是有可能互相影响的。

1
10 10
4 3 8 4 2 4 4 4 4 2 
9 6 8
7 1 4
2 5 5
8 1 8
7 4 6
9 7 8
6 8 8
8 4 5
9 10 5
3 1 9

当然，我们发现我们的贪心结论是没有什么大的问题的，只是适用范围错了，其仅在倒推时，不涉及传递的时候有用。

P1439 【模板】最长公共子序列

Posted on 2025-06-02 Edited on 2026-02-17

思路讲解

https://www.luogu.com.cn/article/63o898db

如果说一个序列是1，2，3，4，5，……，N，还有一个序列无序，那么其实就选一个LIS就行。

那么现在前面这个序列不是有序的，但前面这个序列的标号是有序的，这个时候怎么搞？其实我们就定义新的顺序为A[1]<A[2]<A[3]……<A[N]，就行了

scanf("%lld",&N);
FOR(i,1,N) {scanf("%lld",&A[i]);posA[A[i]]=i;}
FOR(i,1,N) {scanf("%lld",&B[i]);}
vector<ll> dp;
FOR(i,1,N){
	if(dp.empty()) dp.pb(posA[B[i]]);
	else{
		vector<ll>::iterator it=lower_bound(all(dp),posA[B[i]]);
		if(it==dp.end()) dp.pb(posA[B[i]]);
		else dp[it-dp.begin()]=posA[B[i]];
	}
}
printf("%d\n",SZ(dp));

AC代码

https://www.luogu.com.cn/record/219257679

源代码

// Problem: P1439 【模板】最长公共子序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1439
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.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())
#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 getFro(vec) (vec.empty()?0:vec.front())
// #define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
// #define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
// variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
// #define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
// var.end())-var.begin());} while (0)
// #define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
// std::cerr<<"\n"; }while(0)
// #define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
// & pair : variable) \
// { std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
// std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
// #define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e5)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],B[MAXN];
/*

*/
ll posA[MAXN];
inline void solve(){
	scanf("%lld",&N);
	FOR(i,1,N) {scanf("%lld",&A[i]);posA[A[i]]=i;}
	FOR(i,1,N) {scanf("%lld",&B[i]);}
	vector<ll> dp;
	FOR(i,1,N){
		if(dp.empty()) dp.pb(posA[B[i]]);
		else{
			vector<ll>::iterator it=lower_bound(all(dp),posA[B[i]]);
			if(it==dp.end()) dp.pb(posA[B[i]]);
			else dp[it-dp.begin()]=posA[B[i]];
		}
	}
	printf("%d\n",SZ(dp));
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	// scanf("%lld",&lT);
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/219257679
*/