题目概述

CF1442B

解题报告

定义一个新数组 $A_i$ 表示 $b_i$ 在 $\{a_n\}$ 中的下标，然后将 $\{a_n\}$ 递增排序，问题转化为在 $\{a_n\}$ 中选出 $A$ 数组。显然这两个问题等价。

经过观察，我们可以发现一个性质：在处理 $A_i$ 时（前面已经处理好了并且可行），如果 $A_i>1$ ，则 $1\sim A_i-1$ 中必定存在一个元素没有被删去，如果 $A_i<n$ ，则 $A_i+1\sim n$ 中必定存在一个元素没有被删去。

如果 $A_i>1$ 时，$1\sim A_i-1$ 中的元素全被删去了，说明 $1\sim A_i-1$ 的位置全部在 $A_i$ 之前被添加到了 $A$ 中，但是如果不删掉 $A_i$ 或者提前处理 $A_i$ ，这是不可能做到的，因此必定无解。$A_i+1\sim n$ 同理。

也就是说处理到 $A_i$ 的时候，左右两边一定有相邻的元素存在，除非 $A_i=1$ 或 $A_i=n$ 。

但是需要注意，如果处理 $A_i$ 的时候 $A_i-1$ 或者 $A_i+1$ 还没被处理，那么就不能取左边或者右边。

所以对于每个 $A_i$ 求出可取相邻元素的个数乘起来就是方案数。

示例程序

#include<cstdio>
using namespace std;
const int maxn=200000,MOD=998244353;

int te,n,m,ID[maxn+5],a[maxn+5],vis[maxn+5],ans;

int main(){
    for (scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&m);ans=1;
        for (int i=1,x;i<=n;i++) scanf("%d",&x),ID[x]=i,vis[i]=false;
        for (int i=1;i<=m;i++) scanf("%d",&a[i]),a[i]=ID[a[i]],vis[a[i]]=true;
        for (int i=1;i<=m;i++){
            int now=0;
            if (a[i]>1 && !vis[a[i]-1]) now++;
            if (a[i]<n && !vis[a[i]+1]) now++;
            ans=ans*now%MOD;vis[a[i]]=false;
        }
        printf("%d\n",ans);
    }
    return 0;
}