The 2022 ICPC Asia Regionals Online Contest (II) G

G Good Permutation

For a permutation P of length n, we define mxl,r​=maxi=lr​Pi​,mnl,r​=mini=lr​Pi​

For a permutation, we call it the good interval if and only if mxl,r​−mnl,r​=r−l for a interval [l,r](1≤l≤r≤n).

You have some requirements for permutations, you hope that the generated permutations have some good intervals, Specifically, you have m restrictions, and the i th restriction requires the interval [l,r] to be a good interval ,and you want to know the number of such permutations. The answer can be very large, you need to output the result of the answer modulo 10^9+7. The input guarantees that for any two restrictions, there are only inclusive and disjoint relations.

输入格式:

The first line contains two positive integer n,m (1≤n,m≤10^6), indicating the length of the permutation and the number of restrictions.

The next m lines, each line contains two positive integers li​,ri​(1≤li​≤ri​≤n), indicating the ith restriction.

For any two restrictions 1≤i,j≤m, if li​>lj​, then ri​≤rj​ or rj​

输出格式:

Output a line with a positive integer indicating the number of permutations that meet the requirements.

输入样例:

5 3
1 5
1 4
1 3

输出样例:

24

代码长度限制

16 KB

时间限制

1000 ms

内存限制

256 MB

树形dp

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef double db;
const int N=1e6+10;
const int mod=1e9+7;
int n,m;
int fac[N];
vector<int>st[N],ed[N],g[N];
int len[N];
int dfs(int u)
{
    int res = 1;
    int s = 0;
    for (int v : g[u])
    {
        res *= dfs(v);
        s += len[v];
        res %= mod;
    }
    res *= fac[len[u] - s + g[u].size()];
    res %= mod;
    return res;
}
void solve()
{
    fac[0]=1;
    for(int i=1;i<=N;i++)
    {
        fac[i]=i*fac[i-1]%mod;
    }
    cin>>n>>m;
    vector<pair<int,int>>pp;
    pp.push_back({ 0,0 });
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l >>r;
        pp.push_back({ l,r });
    }
    sort(pp.begin(),pp.end());
    for(int i=1;i<pp.size();i++)
    {
        if (pp[i]!=pp[i-1])
        {
            int L=pp[i].first,R=pp[i].second;
            len[i]=R-L+1;
            st[L].push_back(i);
            ed[R].push_back(i);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        sort(st[i].begin(), st[i].end(), [](int a, int b)
        {
            return len[a] > len[b];
        });
        sort(ed[i].begin(), ed[i].end(), [](int a, int b)
        {
            return len[a] < len[b];
        });
    }
    stack<int>stk;
    stk.push(0);
    for (int i=1;i<=n;i++)
    {
        for (int x : st[i])
        {
            stk.push(x);
        }
        for (int x : ed[i])
        {
            if (x == stk.top())
            {
                stk.pop();
                int fa = stk.top();
                g[fa].push_back(x);
               // cout<<fa<<" "<<x<<"\n";
            }
        }
    }
    len[0] = n;
    cout<<dfs(0)<<"\n";
}
signed main()
{
 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
 
 
    return 0;
}