题解：AT_awtf2025_b Movies

首先如果集合确定，有一个简单的贪心做法，把所有集合按照右端点升序排序，右端点相同按照左端点升序排序，对于当前考虑的区间 $[L, R]$ 和当前每天看电影 / 没看电影的局面，从 $[L, R]$ 中找到最小的一天，满足这天没看电影，然后让这天看电影。如果不存在这样一天，无影响。

然后就是这种题的常规想法，拆贡献，但由于各种区间、天之间互相纠缠、互相影响，不好算有多少种集合使得某一天一定看电影。但是观察贪心过程可以注意到，“极长区间”很有意义，也就是说枚举极长的看电影连续段 $[l, r]$，使得 $l - 1$ 和 $r + 1$ 没看，且 $l \sim r$ 都看了。

但是直接考虑极长连续段，也不好算，继续寻找性质。如果我们枚举的极长区间是 $[l, r]$，同时集合中存在一个区间 $[L_i, R_i]$ 使得 $L_i \not \in [l, r]$，如果 $L_i > r$，那么这个区间显然对 $[l, r]$ 无影响，如果 $L_i < l$，这个区间可能对 $[l, r]$ 产生影响，但产生影响的必要条件是 $l - 1$ 看电影了，所以不符合我们的钦定。

于是乎，设 $t_{l, r}$ 表示所有 $L_i \in [l, r]$ 的区间组成的集合，求 $f_{l, r}$ 表示，有多少个 $t_{l, r}$ 的子集，使得 $[l, r]$ 是极长连续段。如果求出了 $f_{l, r}$，由于当 $[l_1, r_1] \cap [l_2, r_2] = \varnothing$ 的时候，$t_{l_1, r_1}$ 和 $t_{l_2, r_2}$ 不交，两者的 $f$ 值可以直接相乘，所以后面的东西就简单了，直接用一个 $n^2$ 个状态的二维 dp。dp 转移的时候要注意，我们钦定的这些极长连续段不仅不能相交，还不能相邻。

考虑怎么求 $f_{l, r}$。注意最开始我们的贪心，这个贪心给了我们一个考虑区间的顺序，所以把输入的区间排好序，设 $f_{i, l, r}$ 表示考虑了前 $i$ 个区间，当前的 $f_{l, r}$ 的值。

当加入区间 $[L, R]$ 的时候：

算出 $f$ 后直接用前面说的 dp 就行了。复杂度 $O(n^5)$，但是常数非常小。