Limited Permutation

题目链接

题意

有$n$个元素的全排列的合法性定义为：有$n$个区间，对于第$i$个区间$[l_{i},r_{i}]$有$l_{i} \leq i \leq r_{i}$,对于任意$1 \leq L \leq i \leq R \leq n$.
当且仅当$l_{i} \leq L \leq i \leq R \leq r_{i}$时,$P[i]=min(P[L],P[L+1],...,P[R])$。现在给出序列和相应的区间，问多少区间是否合法？

思路

我们可以先确定的是，这些区间一定是要么包含关系，要么交集为空，而且我们还知道，排列中最小数字的位置左端点一定是$1$，右端点一定是$n$。
我们把$n$个区间进行排序，优先左端点升序，然后右端点降序。这样第一个区间的位置$i$一定放最小的数字，$i$将数列分成两段，我们把$2$到$n$中$i-1$个数放到左边，剩下放到右边，相当于解决一个子问题，答案更新: $ans = ans \times C_{n-1}^{i-1}.$

ll dfs(int l, int r) {
    if (l > r) return 1;
    if (a[rear].l != l || a[rear].r != r)
        return 0;
    node now = a[rear++];
    ll ret = C(now.r - now.l, now.id - now.l) * dfs(now.l, now.id - 1) % mod;
    ret = (ret * dfs(now.id + 1, now.r)) % mod;
    return ret;
}