题解：CF1976E Splittable Permutations

· · 题解

题意

对于一个数组，每次遵守以下规则将其分成两个数组：

给定你操作次数 q ，以及 l,r 数组，求满足题意的初始长度为 n 的排列数量。

Sol

模拟切割操作，发现可以确定出现元素的相对顺序，具体来说就是 l_i 出现在 r_i 左边，根据题目的分割的性质，若 i<j，满足 r_i=r_j，一定有 l_i 在 l_i 左边，可以考虑用链表维护其相对顺序。

接下来考虑插入未确定的元素，由于每次切割有最大值的限制，插入 x 必须插入在比它大的元素旁边，这样才能保证切割后，不会影响到另一边的最大值。

由于随着 x 的减小，比它大的元素的增多，具有单调性，更具体来说，满足前缀和。

不妨设 f_x 表示 x 能放的缝隙数量，考虑每个缝隙，让其贡献放到较大的位置上，这是因为当 a_{i+1}<x<a_i，这个缝隙已经可以放元素了，记 g_x 表示放完 x 后增加的可以多放位置数。

对于在链表中的 a_i，g_{a_i}=[a_i>a_{i-1}]+[a_i>a_{i+1}]。

对于不在链表中的 x，g_x=1，因为 x 必须放在 y>x 的旁边，y 旁边的位置统计过了，增加的位置在 x 右边。

答案就是：

f_x=f_{x+1}+g_{x+1} res=\prod_{x\notin a}f_x

时间复杂度 O(n) 。

感觉描述的好抽象。

Code

#include<bits/stdc++.h>
#define ll long long
#define N 300005
#define endl "\n" 
#define fi first
#define se second
using namespace std;
const ll mod=998244353;
const ll inf=1e18;
const double eps=1e-6; 
ll n,m,l[N],r[N];
ll a[N],x[N],y[N],cnt[N];
vector<ll>v;
void sol(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>x[i];
    for(int i=1;i<=m;i++)cin>>y[i];
    l[x[1]]=0;
    r[0]=x[1];
    a[x[1]]=x[1];
    for(int i=1;i<=m;i++){
        if(a[x[i]]){
            a[y[i]]=y[i];
            r[y[i]]=r[x[i]];
            l[y[i]]=x[i];
            l[r[x[i]]]=y[i];
            r[x[i]]=y[i];
        }else{
            a[x[i]]=x[i];
            r[x[i]]=y[i];
            l[x[i]]=l[y[i]];
            r[l[y[i]]]=x[i];
            l[y[i]]=x[i];
        }
    }
    for(int j=r[0];j;j=r[j])v.push_back(j);
    cnt[v[0]]=1,cnt[v.back()]=1;
    for(int i=1;i<v.size();i++)cnt[max(v[i],v[i-1])]++;
    ll res=1,ans=0;
    for(int i=n;i>=1;i--){
        if(!a[i]){
            res=res*ans%mod;
            ans=(ans+1)%mod;
        }
        ans=(ans+cnt[i])%mod;
    }
    cout<<res<<endl;
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ll ttt=1;
    while(ttt--)sol();
    return 0;
}