题解

思路

设 $dp_{l,r}$ 表示只考虑区间 $[l,r]$ 内完全包含的条件时，这一段相对大小排列的合法方案数。

做法

枚举该区间最大值所在位置 $k$：若存在某个满足 $l\le L_i\le R_i\le r$ 且 $X_i=k$ 的条件，则这个位置不能放最大值；否则跨过 $k$ 的条件已经由最大值保证成立，剩余条件分别落入左右两段。左右两段的值集合可以从其余 $r-l$ 个值中任选，因此转移贡献为 $dp_{l,k-1}dp_{k+1,r}\binom{r-l}{k-l}$，空区间的方案数视为 $1$。

为快速判断位置是否被禁止，对每个右端点 $r$ 和位置 $k$ 预处理所有满足 $R_i\le r、X_i=k$ 的条件中最大的 $L_i$；该最大值不小于当前 $l$ 时，$k$ 就不可选。组合数用杨辉三角预处理，按区间长度递增计算 DP。

复杂度

时间复杂度为 $O(N^3+N^2+M)$，空间复杂度为 $O(N^2)$。