CF1558D Top-Notch Insertions

· · 题解

题目描述

点此看题

考虑对一个长度为 n 的数组 a 进行插入排序，对于每个位置 i，如果 a_{i-1}\leq a_i 那么不需要进行插入排序；否则找到第一个位置 j 满足 a_i<a_j 把 a_i 插入到 a_j 的前面，此时我们记录下插入信息 (i,j)

现给出 m 个插入信息 (x_i,y_i)，问有多少个初始序列 a 的插入排序恰好能对应给定的插入信息。

n\leq 2\cdot 10^5,m\leq 2\cdot 10^5$，多组数据**只保证** $\sum m\leq 2\cdot 10^5

解法

这道题是真的难，但是我一个学弟随便切掉了。

考虑初始序列 a 是 [a_1,a_2,a_3,a_4,a_5]，如果给出的插入信息是 (3,1),(4,1),(5,3)，那么可以唯一确定排序后的结果是 [a_4,a_3,a_5,a_1,a_2]，所以初始序列唯一对应一个排序序列，并且由于插入过程确定，所以排序序列也唯一对应一个初始序列，那么初始序列和排序序列构成一个双射，问题可以转化成对排序序列的计数。

还是用上面的例子，由排序序列可以得到限制 a_4\leq a_3\leq a_5\leq a_1\leq a_2，我们考虑插入过程中还带来了什么限制：

设排序序列 b 有 c 个位置满足 b_i<b_{i+1}（注意并不完全是上面所谓的”限制“个数和，因为如果 a_{i1},a_{i2} 同时插入到 a_j 的后面那么最终只会产生一个小于号），显然这是一个组合数问题，先把 b 差分，然后可以转化成有 n+1 个未知数，其中有 c+1 个未知数要求为正，要求和为 n，利用隔板法可知解的个数是 {2n-1-c\choose n}

现在的问题就是求 c 嘛，考虑关键的地方是要看 a_j 是否之前就被插入了，如果没有才让 c\leftarrow c+1，可以用平衡树维护，按题目给的插入信息来模拟，如果 a_j 不在平衡树就相当于没有被插入过，然后打标记来维护插入后的整体平移即可，时间复杂度 O(m\log n)

总结

一开始我想根据题目的限制建拓扑图，但是这样会多出来很多无用的限制反而不好考虑，所以一定要去除无效限制，本题就是用考虑排序序列的方法去除了很多无效限制。

计数问题要找映射关系，如果有双射关系很可能有大用处。

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
const int M = 400005;
const int MOD = 998244353;
#define int long long
int read()
{
    int x=0,f=1;char c;
    while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
    while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
int T,n,m,fac[M],inv[M];
void init(int n)
{
    fac[0]=inv[0]=inv[1]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
    for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD;
}
int C(int n,int m)
{
    if(n<m || m<0) return 0;
    return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
namespace treap
{
    int rt,cnt,ch[M][2],val[M],hp[M],tg[M];
    void clear()
    {
        for(int i=1;i<=cnt;i++)
            ch[i][0]=ch[i][1]=val[i]=tg[i]=0;
        rt=cnt=0;
    }
    struct node
    {
        int p[2];
        node() {p[0]=p[1]=0;}
    }emp;
    void add(int x,int v)
    {
        if(!x) return ;
        val[x]+=v;tg[x]+=v; 
    }
    void down(int x)
    {
        if(!tg[x]) return ;
        add(ch[x][0],tg[x]);
        add(ch[x][1],tg[x]);
        tg[x]=0;
    }
    node split(int x,int v)
    {
        if(!x) return emp;
        int d=val[x]<=v;down(x);
        node y=split(ch[x][d],v);
        ch[x][d]=y.p[d^1];
        y.p[d^1]=x;
        return y;
    }
    int merge(int x,int y)
    {
        if(!x || !y) return x+y;
        if(hp[x]<hp[y])
        {
            down(x);
            ch[x][1]=merge(ch[x][1],y);
            return x;
        }
        down(y);
        ch[y][0]=merge(x,ch[y][0]);
        return y;
    }
    int get(int x)//creat an element x
    {
        cnt++;val[cnt]=x;
        hp[cnt]=rand();
        return cnt;
    }
    int find(int x)//exist x? 
    {
        node t=split(rt,x-1),w=split(t.p[1],x);
        if(w.p[0]>0)//exist
        {
            add(w.p[0],1);add(w.p[1],1);
            rt=merge(t.p[0],merge(w.p[0],w.p[1]));
            return 0;
        }
        //if not,we need to insert
        w.p[0]=merge(get(x),w.p[1]);
        add(w.p[0],1);
        rt=merge(t.p[0],w.p[0]);
        return 1;
    }
}
signed main()
{
    T=read();init(4e5);
    while(T--)
    {
        n=read();m=read();
        treap::clear();int ans=0;
        for(int i=1;i<=m;i++)
        {
            int a=read(),b=read();
            if(treap::find(b)) ans++;
        }
        printf("%lld\n",C(2*n-ans-1,n));
    }
}