#P17725. [2026年福建省队集训]拱心石
[2026年福建省队集训]拱心石
题目描述
柏雷塔尼亚被无色浓雾吞噬,古老兽苏醒,恶魔肆虐。为了封印古老兽,要人决定在裂隙中重新降下 座全新的拱心石,分别标记为 号、 号和 号。这 座拱心石将作为锚点,净化周边的世界(它们在平面上的位置可以重合)。
此时,平面上盘踞着 个恶魔,第 个恶魔的结界范围是一个边平行于坐标轴的矩形。
作为引路人,你需要为每个恶魔结界指定恰好一座用来镇压它的拱心石,从而得到一个封印序列 。
一个封印序列被称作是"稳定的",当且仅当存在一种在平面上放置这 座拱心石的方案,使得每一个恶魔的结界内部(或边缘),都至少包含它被指定的那座拱心石,从而使其力量被彻底压制。
恶魔力量错综复杂,矩形结界可能会互相重叠。问有多少个稳定的封印序列?答案对 取模。
输入格式
第一行包含一个正整数 ,表示盘踞在平面上的恶魔总数。
接下来 行,第 行包含四个整数 ,用空格隔开,定义第 个恶魔结界矩形的左下角坐标为 ,右上角坐标为 。
输出格式
输出一行一个整数,表示稳定的封印序列总数对 取模后的结果。
样例 1 输入
4
1 2 3 2
1 2 1 3
1 3 3 3
2 1 4 3
样例 1 输出
36
数据范围与约定
对于所有测试数据,保证 ,且所有恶魔结界的坐标满足 ,。
本题采用多子任务测试,具体子任务限制如下:
。局势极其明朗,恶魔数量稀少。
。无色浓雾初现,结界规模有限。
。恶魔爪牙渐多,结界相互交错。
$\operatorname{Subtask} 4 (5\%):\max\{lx_i\} \le \min\{rx_i\}$ 且 。所有恶魔的结界存在一个庞大的核心交集。
$\operatorname{Subtask} 5 (15\%):\max\{lx_i\} \le \min\{rx_i\}$ 或 。恶魔的结界在至少一个维度上存在横跨所有领地的共性长廊。
无特殊限制。柏雷塔尼亚全面沦陷,混沌的时空等待真正的引路人来重构秩序。