题解：CF1976E Splittable Permutations

· · 题解

题解：CF1976E Splittable Permutations

题目描述

定义一次操作是把一个序列分成两个非空子序列，然后把他放到整个序列的集合之中。

这次操作的 l_i 是左边序列的最大值，r_i 是右边序列的最大值。

现在给定你 l_i 和 r_i，求有多少种 1 \sim n 的排列可以找到一种操作方式满足给定的条件。

思路

首先可以发现，我们可以确定最终整个序列中每一个序列的最大值。

如果要把一个序列分成两份，就可以插入一个新的节点，最终会形成一个双端队列。

然后考虑如何把剩下的数加进来。

对于一个没有加进来的数，它可以插入的地方当且仅当旁边两个数有一个比他大，这样就可以跟着一个“大哥”一直走下去。

插入每个数的时候把答案相乘，利用乘法原理，但是如何使得答案更大？

再发现一点，如果 x 越小，那么其可以插入的缝隙就越多，所以我们考虑从大往小插入即可。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int maxn=3e5+10;
int nxt[maxn],pre[maxn];
bool b[maxn];
struct node{
    int x,y;
}arr[maxn];
int da[maxn];
signed main(){
    int n,q;
    scanf("%lld%lld",&n,&q);
    b[n]=true;
    nxt[n]=n+1;
    pre[n+1]=n;
    nxt[0]=n;
    pre[n]=0;
    for(int i=1;i<=q;i++){
        scanf("%lld",&arr[i].x);
    }   
    for(int i=1;i<=q;i++){
        scanf("%lld",&arr[i].y); 
    }
    for(int i=1;i<=q;i++){
        if(b[arr[i].x]){
            b[arr[i].y]=true;
            int k=nxt[arr[i].x];
            nxt[arr[i].y]=k;
            pre[k]=arr[i].y;
            nxt[arr[i].x]=arr[i].y;
            pre[arr[i].y]=arr[i].x;
        }else{
            b[arr[i].x]=true;
            int k=pre[arr[i].y];
            nxt[k]=arr[i].x;
            pre[arr[i].x]=k;
            nxt[arr[i].x]=arr[i].y;
            pre[arr[i].y]=arr[i].x;
        }
    }
    int p=nxt[0];
    da[p]++;
    while(nxt[p]!=n+1){
        int k=nxt[p];
        da[max(k,p)]++;
        p=nxt[p];
    }
    p=pre[n+1];
    da[p]++;
    int res=0,ans=1;
    for(int i=n;i>=1;i--){
        res+=da[i];
        if(!b[i]){
            ans=ans*res%mod;
            res++;
        }
    }
    printf("%lld",ans);
}