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

weifengzhaomi · 2025-08-21 20:04:51 · 题解

看了一下别人的代码，貌似没有和我一样的？

题目意思比较明了，这里不在复述。

思路

首先我们观察题目，发现 a 和 b 数组都是一个排列，这意味着每个数在 b 中都有唯一的位置。

不难想到我们可以用一个 c 数组，来存储每个 a_i 在 b 数组中的位置。

那么，问题就转化成了：统计 c 数组中所有递增的非空连续子段的数量。

这是因为要使得 a 的连续子段是 b 的子序列，当且仅当对应的 c 的子段是递增的。

最后，要注意的是爆int。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[1000010],b[1000010],c[1000010],d[1000010],ans,cnt = 1;
signed main(){
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) cin >> b[i],c[b[i]] = i;
    for (int i = 1;i <= n;i++) d[i] = c[a[i]];
    for (int i = 1;i <= n;i++){
        if (i > 1 && d[i] <= d[i - 1]) cnt = i;
        ans += i - cnt + 1;
    }
    cout << ans << endl;
}