题解：CF1976E Splittable Permutations

DYYqwq · 2026-11-11 16:00:59 · 题解

容易想到题意就是告诉你若干个固定区间的 \max，让你构造满足这些条件的排列数。

首先如何算出固定的区间：类似最值分治的，可以建出树。对于一个大区间，我们分成左右两个小区间，一定有一个区间的最值是不变的，不变的区间不作为儿子出现，而变化的区间看是 l 还是 r 来决策挂在左儿子还是右儿子。我们可以不显式建树，而选择用双向链表维护树结构。如加入左儿子就是在本节点紧左侧插入新点，而树的中序遍历恰好就是双向链表的顺序，同样也是序列顺序。

对于答案统计部分，因为限制都是最大值，所以考虑从大向小依次插入所有值。

• 对于非区间最值的值，插入任何区间最值大于它的区间都是合法的。我们记录当前只考虑区间最值所构成的连通块数为 s（比如你有三个区间，第一个和第三个都填上了最值，第二个区间填了个小数，那当前 s=2）。对于一个连通块，设其长度为 len，我们有 len+1 个位置可以供当前值插入。因此贡献 v=\sum(len+1)=n-i+s。
• 对于区间最值，其被限定死了区间，无法对答案做出贡献。

考虑动态维护 s。在从大到小遍历所有数字的过程中，我们需要保证所有比当前 i 大的最值所对应的区间全部维护到。对于每个区间，判断其左右最值区间是否已经填入值，由此推断是：独立新开一段、延续左边、延续右边，抑或是粘连上了左右两侧，并更新 s。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
int n , q , l[300010] , r[300010];
struct node {int pre , nxt , val;}t[300010];
int pos[300010] , cnt = 0 , b[300010] , c[300010];
bool vis[300010];
int main()
{
    scanf("%d%d" , &n , &q); vector<int> vec;
    for(int i = 1 ; i <= q ; i ++) scanf("%d" , &l[i]) , vec.push_back(l[i]);
    for(int i = 1 ; i <= q ; i ++) scanf("%d" , &r[i]) , vec.push_back(r[i]);
    sort(vec.begin() , vec.end());
    vec.erase(unique(vec.begin() , vec.end()) , vec.end());
    pos[n] = ++ cnt , t[cnt].val = n;
    for(int i = 1 ; i <= q ; i ++)
    {
        int now = pos[l[i]] + pos[r[i]];
        if(pos[l[i]] == 0)
        {
            pos[l[i]] = ++ cnt;
            int pre = t[now].pre;
            t[pre].nxt = t[now].pre = cnt;
            t[cnt].nxt = now , t[cnt].pre = pre , t[cnt].val = l[i];
        }
        else
        {
            pos[r[i]] = ++ cnt;
            int nxt = t[now].nxt;
            t[nxt].pre = t[now].nxt = cnt;
            t[cnt].pre = now , t[cnt].nxt = nxt , t[cnt].val = r[i];
        }
    }
    int head = 1;
    while(t[head].pre) head = t[head].pre;
    for(int i = head , id = 1 ; i != 0 ; i = t[i].nxt , id ++) b[id] = t[i].val , c[t[i].val] = id;
    int m = (int)vec.size();
    int sz = 0; ll ans = 1;
    for(int i = n , j = m - 1 ; i >= 1 ; i --)
    {
        while(j >= 0 && vec[j] > i)
        {
            int x = vec[j]; vis[x] = 1;
            int idx = c[x];
            sz ++;
            if(idx > 1 && vis[b[idx - 1]]) sz --;
            if(idx < m && vis[b[idx + 1]]) sz --;
            j --;
        }
        if(j < 0 || vec[j] != i) ans *= (n - i + sz) , ans %= mod;
    }
    printf("%lld" , ans);
    return 0;
}