#P17725. [2026年福建省队集训]拱心石

[2026年福建省队集训]拱心石

题目描述

柏雷塔尼亚被无色浓雾吞噬,古老兽苏醒,恶魔肆虐。为了封印古老兽,要人决定在裂隙中重新降下 33 座全新的拱心石,分别标记为 11 号、22 号和 33 号。这 33 座拱心石将作为锚点,净化周边的世界(它们在平面上的位置可以重合)。

此时,平面上盘踞着 nn 个恶魔,第 ii 个恶魔的结界范围是一个边平行于坐标轴的矩形。

作为引路人,你需要为每个恶魔结界指定恰好一座用来镇压它的拱心石,从而得到一个封印序列 [c1,c2,…,cn] (ci∈{1,2,3})[c_1, c_2, \dots, c_n]\,(c_i \in \{1, 2, 3\})。

一个封印序列被称作是"稳定的",当且仅当存在一种在平面上放置这 33 座拱心石的方案,使得每一个恶魔的结界内部(或边缘),都至少包含它被指定的那座拱心石,从而使其力量被彻底压制。

恶魔力量错综复杂,矩形结界可能会互相重叠。问有多少个稳定的封印序列?答案对 109+910^9 + 9 取模。

输入格式

第一行包含一个正整数 nn,表示盘踞在平面上的恶魔总数。

接下来 nn 行,第 ii 行包含四个整数 lxi,lyi,rxi,ryilx_i, ly_i, rx_i, ry_i,用空格隔开,定义第 ii 个恶魔结界矩形的左下角坐标为 (lxi,lyi)(lx_i, ly_i),右上角坐标为 (rxi,ryi)(rx_i, ry_i)。

输出格式

输出一行一个整数,表示稳定的封印序列总数对 109+910^9 + 9 取模后的结果。

样例 1 输入

4
1 2 3 2
1 2 1 3
1 3 3 3
2 1 4 3

样例 1 输出

36

数据范围与约定

对于所有测试数据,保证 1≤n≤2.5×1051 \le n \le 2.5 \times 10^5,且所有恶魔结界的坐标满足 1≤lxi≤rxi≤n1 \le lx_i \le rx_i \le n,1≤lyi≤ryi≤n1 \le ly_i \le ry_i \le n。

本题采用多子任务测试,具体子任务限制如下:

Subtask⁡1(20%):n≤15\operatorname{Subtask} 1 (20\%):n \le 15。局势极其明朗,恶魔数量稀少。

Subtask⁡2(25%):n≤150\operatorname{Subtask} 2 (25\%):n \le 150。无色浓雾初现,结界规模有限。

Subtask⁡3(20%):n≤2000\operatorname{Subtask} 3 (20\%):n \le 2000。恶魔爪牙渐多,结界相互交错。

$\operatorname{Subtask} 4 (5\%):\max\{lx_i\} \le \min\{rx_i\}$ 且 max⁡{lyi}≤min⁡{ryi}\max\{ly_i\} \le \min\{ry_i\}。所有恶魔的结界存在一个庞大的核心交集。

$\operatorname{Subtask} 5 (15\%):\max\{lx_i\} \le \min\{rx_i\}$ 或 max⁡{lyi}≤min⁡{ryi}\max\{ly_i\} \le \min\{ry_i\}。恶魔的结界在至少一个维度上存在横跨所有领地的共性长廊。

Subtask⁡6(15%):\operatorname{Subtask} 6 (15\%): 无特殊限制。柏雷塔尼亚全面沦陷,混沌的时空等待真正的引路人来重构秩序。