题解：CF1976E Splittable Permutations

· · 题解

这个题我们建一棵树，这个树类似于笛卡尔树，就是，叶子节点维护出区间的最大值，中间过程节点也是维护两个儿子所对应区间的最大值。

那么我们如何建出这棵树，我们按照输入的顺序，直接建边就行，就是，选出两数的最大值，再去分别向这两棵树连边，

我们从前往后拿出每一个叶子，我们设这个数组为 s。我们再记录一个 vis 表示这个数是否在 s 中出现过。

之后，我们考虑统计答案，我们考虑对于 s 中每个相邻的数，他们之间能放的数一定是比这两个数最大值小的，我们设 cnt_{x} 表示限制正好为 x 的空隙数。

对于每一个没有出现在 s 中的数，我们从大到小排序（我们到后面去讲解为什么从大到小排序），排完序之后，对于当前的数 x，能放的位置就是所有比 x 大的 y 的 cnt_{y} 的和。

吗。哦我们发现这是这是不对的，因为先加进来的数也会对当前位有贡献，就是以前加进来的数可能会产生新的可加入的位置，这个东西怎么处理。我们回想到从大到小排序这一步，考虑到此时在 x 之前加入的数都能够产生一个新的位置。比如说，我们在原序列 7\ 6 之间加入一个 5 原序列就变成了 7\ 5 \ 6，之后我们考虑加入 4，原先能加入的位置的个数为 3，因为 7 的左边的 6 的右边都能够加数，加完 5 之后，能加入 4 的位置变成了 4 个，这是因为 5 将原先的 7\ 6 之间的位置从 1 个变为了 2 个，此时，你可能会问，如果我原来 7 旁边的位置是 3 还是一样的结论吗。答案是一样的，这一步留给读者自己手玩。

之后呢，我们就通过手玩发现了，每一个提前加入的数，无论其插到任何位置，都能对后面产生 1 的贡献，我们从大到小做就对了。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
#define int long long
struct edge{
    int l,r;
}e[300005];
int pos[300005];
int tot=0;
int id[300006*2];
vector<int>g[600005];
int tp=0;
int s[300005];
int vis[300005];
int cnt[300005];
void dfs(int u){
    if(!g[u].size()){
        s[++tp]=id[u];
        vis[id[u]]=1;
    }
    for(int v:g[u]){
        dfs(v);
    }
}
main(){
    int n,q;
    cin>>n>>q;
    pos[n]=++tot;
    id[tot]=n;
    for(int i=1;i<=q;i++){
        cin>>e[i].l;
    }
    for(int i=1;i<=q;i++){
        cin>>e[i].r;
    }
    for(int i=1;i<=q;i++){
        int x=(e[i].l>e[i].r?pos[e[i].l]:pos[e[i].r]);
        pos[e[i].l]=++tot;
        g[x].push_back(tot);
        id[tot]=e[i].l;
        pos[e[i].r]=++tot;
        g[x].push_back(tot);
        id[tot]=e[i].r;
    }//这是整个建树的过程
    dfs(1);
    int sum=0;
    for(int i=0;i<=tp;i++){
        cnt[max(s[i],s[i+1])]++;
    }
    int ans=1;
    for(int i=n;i>=1;i--){//从大到小统计答案
        sum+=cnt[i];
        if(!vis[i]){
            ans*=sum;
            ans%=mod;
            sum++;
        }
    }
    cout<<ans;
    return 0;
}