Luogu5464 缩小社交圈

题意：给出一个大小为 的区间集合 。

对于区间集合 ，定义其 SAN 图为：将相交的两个区间之间连边之后产生的图。

若 SAN 图是一棵树，则称集合 是好的。

求 的好的子集的个数，答案对 取模。

，时限 。

---

SAN 图是一棵树 $$ 图中无环。

又不难发现，任意的一个环必然导出三元环，所以只需要求图中无三元环，即任意三个区间交集为空。

我们将区间按照左端点排序，逐个加入。

为了判定新的区间是否会形成三元环，只需记录前面区间的最右端点和次右端点。

此时也可以判定新的区间是否和旧的区间集合联通。

设 表示（考虑了前若干个区间），最右侧区间为 ，次右区间为 的方案数。

当加入新区间 时：

当且仅当 时转移才合法。若 则产生环，若 则不连通。

接下来要把新区间插入到“最右，次右”的序列中。显然已有 。

• ①

• ②

列出完整的转移式子：

注意 中 是固定的，所以总共只有 次求和。

暴力求和是 的，若使用树状数组优化可以做到 。

不难发现我们新产生的 都是“一层”，按照特殊顺序求前缀和即可做到 。