题解：P13788 「CZOI-R6」Permutation and Subsequence

· · 题解

题意

你需要求出有多少个 a 的 非空 连续子段是 b 的子序列。

分析

把 a 按照 1,2,3,...,n 的顺序映射，b 更 a 一起映射，因为 a 是排列，所以数组即可。

原因：简化问题

现在只需要在 b 中找连续的求数量即可，用 DP 解决。

具体见代码。

Code

#include<bits/stdc++.h>
using namespace std; 
#define int long long
const int N=1e6+5,inf=1e14;
int n;
int a[N],b[N],c[N],d[N];
int dp[N],ans;
//dp[i]=表示b中第i个数连续的数量
//dp[i]=dp[d[b[i]-1](i表示的数的上一个)]+1 预处理d
//all=0
//ans=sum(dp)
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],c[a[i]]=i,a[i]=i;//用数组映射a
    for(int i=1;i<=n;i++)
        cin>>b[i],b[i]=c[b[i]],d[b[i]]=i;//预处理d
    for(int i=1;i<=n;i++){
        dp[i]+=dp[d[b[i]-1]]+1;ans+=dp[i];
    }
    cout<<ans;
    return 0;
}
/*
old:
3 5 2 4 1
2 4 5 3 1 

new:
1 2 3 4 5
3 4 2 1 5
*/