0813科大讯飞笔试 第三题 个人思路

思路

其实就是统计两个排列之间相同的子数组个数，用总的子数组个数减去重复的即可。

我们把第一个排列当作是基准数列，意思是第一个序列是我们规定的从小到大的排序。

根据第一个排列处理第二个排列，得到新的 如果第二个排列的某个区间是1，2，3..这样递增的，那么这个区间的子数组就是重复的，减去即可。

时间复杂度

O(n)

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 2e5+9;
int a[N],b[N];
int pos[N],c[N];
signed main() {
	
	int n;
	cin>>n;
	for(int i=1; i<=n; ++i) cin>>a[i],pos[a[i]]=i;
	for(int i=1; i<=n; ++i) cin>>b[i],b[i]=pos[b[i]];
	int ans=n*(n+1); //如果 
	for(int i=1; i<=n; ++i){
		int j=i+1;
		while(j<=n){
			if(b[j-1]!=b[j]-1) break;
			c[j++]=1;
		}
		//i~j-1就是递增的 ,递增的就会重复 
		int nn = j-i;
		ans-=nn*(nn+1)/2;
		i=j-1;
	//	cout<<ans<<endl;
	}
	cout<<ans<<'\n';
	return 0;
}
/*
3
1 2 3
2 3 1

3
1 2 3
1 3 2

3
2 3 1
1 2 3


*/