[EC Final 2022] Rectangle

形式化题目

固定 $M = 10^9$ 。给出 $n$ 个两两可以重叠的矩形，第 $i$ 个矩形是 $\{(x,y) : x_{i,1}\leqslant x\leqslant x_{i,2},\ y_{i,1}\leqslant y\leqslant y_{i,2}\}$ ，四个坐标都是 $[1,10^9]$ 内的整数，且 $x_{i,1}<x_{i,2}$ 、 $y_{i,1}<y_{i,2}$ 。

一条直线可以是 $x=a$ 或 $y=a$ （ $a\in[1,M]$ 为整数），它与矩形相交当且仅当它与矩形的闭区域有公共点，即 $x=a$ 交于某个矩形 $\iff x_{i,1}\leqslant a\leqslant x_{i,2}$ 。

要求选出三条互不相同的直线，使得每个矩形都至少被其中一条碰到；三条线的先后顺序不计。求方案数对 $998244353$ 取模。

输入 $T$ 组数据， $T\leqslant 10^5$ ， $\sum n\leqslant 2\times 10^5$ 。

样例 #1 的第 1 组只有一个矩形 $[1,M]\times[1,M]$ ：三条线都必须是竖线或都是横线（否则总有一类方向缺线），且 $x=M$ 与 $y=M$ 这两条线能碰到它，于是答案是 $2\binom{M}{3}+2M\binom{M}{2}\equiv 230616300$ ；第 2 组是三个互不相邻的小矩形，答案为 $64$ 。

暴力解法

思路

最直接的做法是枚举三条直线：所有可选的直线共有 $2M$ 条，从中选三条的方案数是 $\binom{2M}{3}$ ，对每种方案逐一检查 $n$ 个矩形，复杂度 $O(M^3n)$ ，在 $M=10^9$ 时完全不可能。

但暴力可以沿「压掉 $M$ 」的方向优化。关键观察是：一条线 $x=a$ 能碰到哪些矩形，只取决于它落在哪些断点之间。把所有 $x_{i,1}$ 和 $x_{i,2}+1$ （再补上 $1$ 与 $M+1$ ）排序去重，就把 $[1,M]$ 切成了若干类：同一类内的所有 $a$ 命中完全相同的矩形集合。设类 $c$ 的长度为 $w_c$ （类中整数个数），命中掩码为 $\text{mask}_c$ ， $y$ 轴同理。

于是「选三条线」可以化为「选三个类，然后从类里选具体取值」。三类下标 $i\leqslant j\leqslant k$ ：

三个下标互不相同：贡献 $w_i w_j w_k$ ；
恰有两个相同（ $i=j\ne k$ 或 $i\ne j=k$ ）：例如从第 $i$ 类里选 $2$ 个不同取值、第 $k$ 类里选 $1$ 个，贡献 $\binom{w_i}{2}w_k$ ；
三个都相同：贡献 $\binom{w_i}{3}$ 。

三类的掩码并集等于全体矩形时该组合才合法。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 13:53
 */
// brute.cpp：正确性优先的暴力解，用于对拍。
//
// 坐标可能到 1e9，无法直接枚举每条线，但「一条线的命中集合」只会在一组
// 断点处改变：x 轴上断点为 {1, M+1} ∪ {x1_i, x2_i+1}，y 轴同理。
// 于是把每个轴划分成若干类区间，同一类内所有取值的命中集合相同。
// 只要枚举「三个类」的组合（含同类重复，因为同一类里可以取多个不同值），
// 用类长度做组合计数即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MX = 1000000000LL;
const ll MOD = 998244353;
const int MAXN = 100005;

int n;
ll rx1[MAXN], ry1[MAXN], rx2[MAXN], ry2[MAXN];

// 一条线：轴（0=x,1=y）、可取值个数 w、命中矩形掩码 mask
struct Line {
    int axis;
    ll w;
    unsigned long long mask;   // n <= 64 时够用，对拍用
};

ll bx[2 * MAXN], by[2 * MAXN];
Line ln[4 * MAXN];

// 组合数 C(x,k)，k=2,3
inline __int128 C2(ll x) { return (__int128)x * (x - 1) / 2; }
inline __int128 C3(ll x) { return (__int128)x * (x - 1) * (x - 2) / 6; }

void solve() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> rx1[i] >> ry1[i] >> rx2[i] >> ry2[i];
        }
        // 两个轴的断点
        int cx = 0, cy = 0;
        bx[cx++] = 1; bx[cx++] = MX + 1;
        by[cy++] = 1; by[cy++] = MX + 1;
        for (int i = 0; i < n; ++i) {
            bx[cx++] = rx1[i];
            if (rx2[i] + 1 <= MX + 1) bx[cx++] = rx2[i] + 1;
            by[cy++] = ry1[i];
            if (ry2[i] + 1 <= MX + 1) by[cy++] = ry2[i] + 1;
        }
        sort(bx, bx + cx); cx = (int)(unique(bx, bx + cx) - bx);
        sort(by, by + cy); cy = (int)(unique(by, by + cy) - by);

        int L = 0;
        // x 轴各类
        for (int k = 0; k + 1 < cx; ++k) {
            ll lo = bx[k], hi = bx[k + 1] - 1;
            if (lo > MX) break;
            unsigned long long mask = 0;
            for (int i = 0; i < n && i < 64; ++i)
                if (rx1[i] <= lo && lo <= rx2[i]) mask |= 1ULL << i;
            ln[L].axis = 0; ln[L].w = hi - lo + 1; ln[L].mask = mask; ++L;
        }
        // y 轴各类
        for (int k = 0; k + 1 < cy; ++k) {
            ll lo = by[k], hi = by[k + 1] - 1;
            if (lo > MX) break;
            unsigned long long mask = 0;
            for (int i = 0; i < n && i < 64; ++i)
                if (ry1[i] <= lo && lo <= ry2[i]) mask |= 1ULL << i;
            ln[L].axis = 1; ln[L].w = hi - lo + 1; ln[L].mask = mask; ++L;
        }

        unsigned long long full = (n >= 64) ? ~0ULL : ((1ULL << n) - 1);
        __int128 tot = 0;
        // 枚举三类的下标 i <= j <= k（同一类可取多个不同值）
        for (int i = 0; i < L; ++i)
            for (int j = i; j < L; ++j)
                for (int k = j; k < L; ++k) {
                    if ((ln[i].mask | ln[j].mask | ln[k].mask) != full) continue;
                    __int128 cnt;
                    if (i == k) cnt = C3(ln[i].w);              // 三者同类
                    else if (i == j) cnt = C2(ln[i].w) * ln[k].w;
                    else if (j == k) cnt = ln[i].w * C2(ln[j].w);
                    else cnt = (__int128)ln[i].w * ln[j].w * ln[k].w;
                    tot += cnt;
                }
        cout << (ll)(tot % MOD) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

复杂度

$x$ 轴与 $y$ 轴各约 $2n+2$ 个类，共 $O(n)$ 个类。枚举三个类需要 $O(n^3)$ ，每次用掩码或运算判合法性，整体 $O(n^3)$ （用 $64$ 位掩码时每次 $O(1)$ ）。它能正确求出答案，但 $n$ 上千就已经很慢，放到 $\sum n\leqslant 2\times 10^5$ 的正式数据上仍然毫无希望。

瓶颈

暴力把三条线当成彼此无关的对象去枚举，而真正决定合法性的信息是「三条线各自覆盖了哪一部分矩形」。要提速，必须按三条线的方向分布分类，并在每一类里把「合法」翻译成区间长度，从而不再枚举具体取值。

正解

思路

按三条线中有几条竖线分类，只有两种非平凡情形（另外两种是它们的转置）：

$3$ 条竖线：记方案数为 $F_1(R)$ ；
$1$ 条横线 $+$ $2$ 条竖线：记方案数为 $F_2(R)$ 。

把每个矩形换成 $(y_{i,1},x_{i,1},y_{i,2},x_{i,2})$ 得到转置后的矩形集合 $R^{\mathsf T}$ ，则

\text{答案}=F_1(R)+F_2(R)+F_1(R^{\mathsf T})+F_2(R^{\mathsf T})\pmod{998244353}.

第一条竖线/横线的处理： $2$ 条横线 $+1$ 条竖线的方案，与「 $1$ 条竖线 $+2$ 条横线」在转置后完全对应，所以只需要实现 $F_2$ 。同理 $3$ 条横线由 $F_1$ 转置得到。

$F_1$ ：三条竖线

设三条竖线为 $x=a_1<a_2<a_3$ ，固定中间那条 $a_2=b$ 。对矩形 $i$ ：

若 $b\in[x_{i,1},x_{i,2}]$ ，它已经被碰到，对 $a_1,a_3$ 没有额外要求；
若 $x_{i,2}<b$ ，则只能靠 $a_1$ 碰到它，要求 $a_1\in[x_{i,1},x_{i,2}]$ ；
若 $x_{i,1}>b$ ，则只能靠 $a_3$ 碰到它，要求 $a_3\in[x_{i,1},x_{i,2}]$ 。

记

S^-(b)=\{i:x_{i,2}<b\},\qquad S^+(b)=\{i:x_{i,1}>b\}.

$a_1$ 必须落在 $\bigcap_{i\in S^-(b)}[x_{i,1},x_{i,2}]$ 内、且 $a_1<b$ ；因为 $S^-$ 中所有矩形都满足 $x_{i,2}<b$ ，下式自动满足上界，故

f_-(b)= \begin{cases} b-1, & S^-(b)=\varnothing,\\[2pt] \max\bigl(0,\ \min\limits_{i\in S^-}x_{i,2}-\max\limits_{i\in S^-}x_{i,1}+1\bigr), & \text{否则};\end{cases}

对称地

f_+(b)= \begin{cases} M-b, & S^+(b)=\varnothing,\\[2pt] \max\bigl(0,\ \min\limits_{i\in S^+}x_{i,2}-\max\limits_{i\in S^+}x_{i,1}+1\bigr), & \text{否则}. \end{cases}

$a_1$ 与 $a_3$ 的约束互不影响，因此中间线为 $b$ 时方案数为 $f_-(b)\,f_+(b)$ ，于是

F_1(R)=\sum_{b=1}^{M} f_-(b)\,f_+(b).

$S^-(b)$ 只在 $b=x_{i,2}+1$ 处变化， $S^+(b)$ 只在 $b=x_{i,1}$ 处变化。把

\{1,\ M+1\}\cup\{x_{i,1}\}\cup\{x_{i,2}+1\}

排序去重得到断点，相邻断点之间（记为 $[lo,hi]$ ）两个集合都不变，于是 $f_-$ 、 $f_+$ 要么是常数、要么是 $b-1$ 或 $M-b$ 这样的线性式，只有四种组合，直接求和：

F_1=\sum_{\text{段}}\Bigl[\text{（空,空）}\ \textstyle\sum(b-1)(M-b)\ +\ \text{（非空,空）}\ cm\sum(M-b)\ +\ \text{（空,非空）}\ cp\sum(b-1)\ +\ \text{（非空,非空）}\ cm\,cp\,\cdot\ \text{len}\Bigr].

其中 $cm,cp$ 是该段上的常值。判断 $S^-$ 是否为空并求 $\min_{S^-}x_2$ 、 $\max_{S^-}x_1$ ，只需把矩形按 $x_2$ 升序排序后取前缀；判断 $S^+$ 同理，把矩形按 $x_1$ 降序排序后取前缀的最小 $x_2$ 与最大 $x_1$ 。所有 $\sum b$ 、 $\sum b^2$ 用等差数列公式 $O(1)$ 算。注意当 $S^-,S^+$ 都为空时 $\sum(b-1)(M-b)$ 可能达到 $M^3/6\approx1.7\times10^{26}$ ，必须用 __int128 累加后在最后取模。

$F_2$ ：一条横线加两条竖线

设横线为 $y=h$ ，两条竖线为 $x=a_1<a_2$ 。记

U_h=\{i:\ h\notin[y_{i,1},y_{i,2}]\}

为横线没有碰到的矩形集合；这些矩形必须全部被某条竖线碰到，而 $U_h$ 之外的矩形已被横线处理完，不再限制竖线。显然 $F_2=\sum_{h=1}^{M}g(U_h)$ ，其中 $g(U)$ 只依赖集合 $U$ 。

记

L=\max_{i\in U}x_{i,1},\qquad R=\min_{i\in U}x_{i,2},\qquad Q(a)=\min\{x_{i,2}:i\in U,\ x_{i,1}>a\}.

若 $a_1\in[L,R]$ ，则 $a_1$ 落在 $U$ 里每个矩形内， $a_2$ 只需 $>a_1$ 即可：贡献 $\sum_{a=L}^{R}(M-a)$ 。
否则，因为 $a_2>a_1$ 且 $R$ 对应的矩形必须被 $a_2$ 碰到，必有 $a_1\leqslant R$ ，所以剩下的只能是 $a_1\in[1,L-1]$ 。此时 $a_1$ 覆盖了所有 $x_{i,1}\leqslant a_1$ 的矩形，其余矩形（ $x_{i,1}>a_1$ ，其中必含 $x_{i,1}=L$ 的那个）必须被 $a_2$ 全部碰到，故 $a_2\in[L,Q(a_1)]$ ：贡献 $\bigl(Q(a_1)-L+1\bigr)^+$ 。

于是

g(U)=\sum_{a=L}^{R}(M-a)\;+\;\sum_{a=1}^{\min(R,\,L-1)}\bigl(Q(a)-L+1\bigr)^{+},

$U=\varnothing$ 时两条竖线任取， $g=\binom{M}{2}$ 。

直接计算 $Q(a)$ 和带正部的求和都是 $O(M)$ 。用恒等式

(S-c)^+ = S-\min(S,c)

把正部去掉，只需计算

\mathrm{Sum}(A,x)=\sum_{a=1}^{A}\min\bigl(Q(a),x\bigr),

则 $H=\mathrm{Sum}(A,+\infty)-\mathrm{Sum}(A,L-1)$ ，其中 $A=\min(R,L-1)$ 。

如何算 $\mathrm{Sum}$ 。 把 $x_1$ 的取值去重排序为 $v_1<\dots<v_m$ ，按 $v$ 建立线段树，第 $j$ 个叶子代表 $a\in[v_{j-1},v_j-1]$ （约定 $v_0=1$ ），权 $w_j$ 为这段长度；叶子的值 $c_j$ 是「 $U$ 中 $x_{i,1}=v_j$ 的矩形的最小 $x_{i,2}$ 」，没有则为 $+\infty$ 。

之所以这样分，是因为当 $a\in[v_{j-1},v_j-1]$ 时， $x_{i,1}>a$ 等价于 $i$ 所在类 $\geqslant j$ ，故

Q(a)=\min_{k\geqslant j}c_k

就是后缀最小值。节点上维护三个量：子树 $c$ 的最小值 $mn$ 、权值和 $sw$ ，以及

sl=\sum_{k\in\text{左子}} w_k\min\bigl(\text{左子内从 }k\text{ 到 }mid\text{ 的后缀最小值},\ mn[\text{右子}]\bigr).

查询 $\mathrm{Sum}$ 时，若某节点整段被覆盖，只需回答 $\sum_k w_k\min(Q'_k,x)$ ——用一个只往一侧递归的 queryCap 即可，代价 $O(\log m)$ ；也正因为如此，pushup 时重算 $sl$ 也只要 $O(\log m)$ ，单点修改总代价 $O(\log^2 m)$ 。

$\mathrm{Sum}(A,x)$ 的区间 $[1,A]$ 会横跨若干完整叶子加一个「被截断的叶子」，从右往左扫一遍完整部分（维护「右侧已扫过部分的最小 $c$ 」作为 $x$ 的额外上界），再单独补上截断部分即可，整体 $O(\log m)$ 。

如何扫描 $h$ 。 矩形 $i$ 在 $h\in[1,y_{i,1}-1]\cup[y_{2,i}+1,M]$ 时属于 $U_h$ ，即它有一个「进入区间」和「离开区间」：

若 $y_{i,1}\geqslant 2$ ，在 $h=1$ 插入（ $1$ 处即生效），在 $h=y_{i,1}$ 删除；
若 $y_{i,2}+1\leqslant M$ ，在 $h=y_{i,2}+1$ 插入。

把 $1$ 处的事件预先执行，之后按 $h$ 从小到大扫，每两个事件之间 $U_h$ 不变，乘上区间长度累加即可。每个叶子用一个 multiset 维护当前激活矩形的 $x_2$ ，插入/删除后其叶值为 multiset 最小值。

对每个测试点， $x_1$ 的类数 $m\leqslant n$ ，插入删除共 $O(n)$ 次、 $g(U_h)$ 只在不同 $h$ 处求值 $O(n)$ 次，总复杂度 $O(n\log^2 n)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 13:53
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 坐标上界：题目中所有坐标都在 [1,1e9]，故 M 恒为 1e9。
// 本地用小 M 压力测试时可加编译选项 -DPROBLEM_M=8 覆盖。
#ifndef PROBLEM_M
#define PROBLEM_M 1000000000LL
#endif
const ll MX = PROBLEM_M;          // 坐标最大值 M
const ll MOD = 998244353;
const int MAXN = 100005;
const ll INF = MX + 1;            // 严格大于任何可能的 x2

int n;
ll rx1[MAXN], ry1[MAXN], rx2[MAXN], ry2[MAXN];

// sum_{i=l}^{r} i
inline __int128 sumB(ll l, ll r) {
    if (l > r) return 0;
    return (__int128)(l + r) * (r - l + 1) / 2;
}

// sum_{i=1}^{t} i^2
inline __int128 sumB2(ll t) {
    if (t <= 0) return 0;
    return (__int128)t * (t + 1) * (2 * t + 1) / 6;
}

// ===============================================================
// 第一部分：三条竖线 x=a1<a2<a3
//
// S^-(b) = {i : x2_i < b}，S^+(b) = {i : x1_i > b}。
// 三条竖线能盖住第 i 个矩形，当且仅当 min(a1,a2) <= x1_i 且 max(a2,a3) >= x2_i。
// 固定 a2=b：a1 必须 <= min{x1_i : i∈S^-}，a3 必须 >= max{x2_i : i∈S^+}。
// 记 f_-(b)、f_+(b) 为 a1、a3 的合法个数，则方案数为 f_-(b)*f_+(b)：
//   f_-(b) = b-1                                        (S^- 为空)
//          = max(0, min_{S^-}x2 - max_{S^-}x1 + 1)       (否则)
//   f_+(b) = M-b                                        (S^+ 为空)
//          = max(0, min_{S^+}x2 - max_{S^+}x1 + 1)       (否则)
//
// S^- 的成员只在 b=x2_i+1 变化，S^+ 只在 b=x1_i 变化；因此以
// {1, M+1} ∪ {x1_i} ∪ {x2_i+1} 为断点分块，块内 f_-、f_+ 的「是否为空」
// 与取值都是常数，统计四类乘积和即可。
// ===============================================================
ll sx1[MAXN], sx2[MAXN];    // 升序的 x1 / x2
ll preMaxX1[MAXN];          // 按 x2 升序后 x1 的前缀最大值
ll preMinX2[MAXN];          // 按 x1 降序后 x2 的前缀最小值
ll bp[2 * MAXN + 5];        // 断点
pair<ll, int> pr[MAXN];     // 排序临时数组

ll case1() {
    for (int i = 0; i < n; ++i) {
        sx1[i] = rx1[i];
        sx2[i] = rx2[i];
    }
    sort(sx1, sx1 + n);
    sort(sx2, sx2 + n);

    // 按 (x2,x1) 升序：前 i+1 个恰是 x2 最小的 i+1 个矩形，记其最大 x1
    for (int i = 0; i < n; ++i) pr[i] = make_pair(rx2[i], rx1[i]);
    sort(pr, pr + n);
    ll cur = 0;
    for (int i = 0; i < n; ++i) {
        if (pr[i].second > cur) cur = pr[i].second;
        preMaxX1[i] = cur;
    }

    // 按 x1 降序：前 i+1 个恰是 x1 最大的 i+1 个矩形，记其最小 x2
    for (int i = 0; i < n; ++i) pr[i] = make_pair(rx1[i], rx2[i]);
    sort(pr, pr + n);
    cur = INF;
    for (int i = n - 1, c = 0; i >= 0; --i, ++c) {
        if (pr[i].second < cur) cur = pr[i].second;
        preMinX2[c] = cur;
    }

    // 断点：S^- 在 x2_i+1 变化，S^+ 在 x1_i 变化
    int bn = 0;
    bp[bn++] = 1;
    bp[bn++] = MX + 1;
    for (int i = 0; i < n; ++i) {
        bp[bn++] = rx1[i];
        bp[bn++] = rx2[i] + 1;
    }
    sort(bp, bp + bn);
    bn = (int)(unique(bp, bp + bn) - bp);

    __int128 tot = 0;
    for (int k = 0; k + 1 < bn; ++k) {
        ll lo = bp[k], hi = bp[k + 1] - 1;
        if (lo > MX) break;
        ll len = hi - lo + 1;
        int i1 = (int)(lower_bound(sx2, sx2 + n, lo) - sx2);       // x2 < lo 的个数
        int cp1 = n - (int)(upper_bound(sx1, sx1 + n, lo) - sx1);  // x1 > lo 的个数
        bool em = (i1 == 0), ep = (cp1 == 0);
        ll cm = 0, cp = 0;
        if (!em) {
            cm = sx2[0] - preMaxX1[i1 - 1] + 1;
            if (cm < 0) cm = 0;
        }
        if (!ep) {
            cp = preMinX2[cp1 - 1] - sx1[n - 1] + 1;
            if (cp < 0) cp = 0;
        }
        __int128 s;
        if (em && ep) {
            // sum (b-1)(M-b) = -(sum b^2) + (M+1)(sum b) - M*len
            s = sumB2(lo - 1) - sumB2(hi)
                + (__int128)(MX + 1) * sumB(lo, hi)
                - (__int128)MX * len;
        } else if (!em && ep) {
            // f_- = cm, f_+ = M-b
            s = (__int128)cm * sumB(MX - hi, MX - lo);
        } else if (em && !ep) {
            // f_- = b-1, f_+ = cp
            s = (__int128)cp * sumB(lo - 1, hi - 1);
        } else {
            s = (__int128)cm * cp * len;
        }
        tot += s;
    }
    return (ll)(tot % MOD);
}

// ===============================================================
// 第二部分：一条横线 y=h，两条竖线 x=a1<a2
//
// U_h = {i : h 不在 [y1_i, y2_i] 内}，即横线没碰到的矩形集合。
// 这两条竖线必须横穿 U_h 中所有矩形，方案数 g(U_h) 只依赖 U：
//   L = max_{i∈U} x1_i，R = min_{i∈U} x2_i。
//   * a2 >= L：只需 a1,a2 <= R，贡献 sum_{a=L}^{R}(M-a)。
//   * a2 <= L-1：记 Q(a)=min{x2_i : i∈U, x1_i>a}，a1 必须 <= Q(a)，
//     贡献 (Q(a)-L+1)^+，对 a=1..min(R,L-1) 求和。
//   U 为空时两条竖线任选，g = C(M,2)。
// 用 (S-c)^+ = S - min(S,c) 去掉正部：
//   H = Sum(A,+INF) - Sum(A,L-1)，其中 Sum(A,x) = sum_{a=1}^{A} min(Q(a),x)。
//
// Sum 用按 x1 取值离散化的线段树维护：
//   叶 j 的权 w_j 表示 a ∈ [v_{j-1}, v_j-1]（v_0=1），
//   叶值 c_j = min{x2_i : x1_i=v_j, i∈U}（无则 INF）。
//   节点维护 mn（子树最小 c）、sw（子树权和）、
//   sl = sum_{k∈左子} w_k * min(左子内后缀min(k..mid), mn[右子])，
//   pushup 时 queryCap 只走一条路径，故 pushup 为 O(log)。
// 随 h 扫描：矩形在 h∈[1,y1-1] ∪ [y2+1,M] 时属于 U，
// 用 multiset 维护每个叶子的激活 x2，插入/删除后单点修改线段树。
// ===============================================================
int m;                        // 不同 x1 值个数
ll vs[MAXN];                  // 去重升序的 x1
int gid[MAXN];                // 每个矩形所在的叶编号
multiset<ll> ms[MAXN];        // 每个叶子当前激活的 x2
ll tmn[4 * MAXN], tsw[4 * MAXN], tsl[4 * MAXN];
vector<pair<int, int> > ev;   // (h, 事件)：正数插入，负数删除

// sum_{k=l}^{r} w_k * min( 后缀min(k..r), y )（对节点整段调用）
ll queryCap(int p, int l, int r, ll y) {
    if (y <= tmn[p]) return tsw[p] * y;
    if (l == r) return tsw[p] * tmn[p];
    int mid = (l + r) >> 1, lc = p << 1, rc = p << 1 | 1;
    if (y <= tmn[rc]) return queryCap(lc, l, mid, y) + y * tsw[rc];
    return queryCap(rc, mid + 1, r, y) + tsl[p];
}

void pushup(int p, int l, int r) {
    int mid = (l + r) >> 1, lc = p << 1, rc = p << 1 | 1;
    tmn[p] = min(tmn[lc], tmn[rc]);
    tsw[p] = tsw[lc] + tsw[rc];
    tsl[p] = queryCap(lc, l, mid, tmn[rc]);
}

void build(int p, int l, int r) {
    tsl[p] = 0;
    tmn[p] = INF;
    if (l == r) {
        ll prev = (l == 1 ? 1 : vs[l - 1]);
        tsw[p] = vs[l] - prev;
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p, l, r);
}

void update(int p, int l, int r, int pos, ll val) {
    if (l == r) { tmn[p] = val; return; }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(p << 1, l, mid, pos, val);
    else update(p << 1 | 1, mid + 1, r, pos, val);
    pushup(p, l, r);
}

ll rangeMin(int p, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return INF;
    if (ql <= l && r <= qr) return tmn[p];
    int mid = (l + r) >> 1;
    return min(rangeMin(p << 1, l, mid, ql, qr),
               rangeMin(p << 1 | 1, mid + 1, r, ql, qr));
}

// 从右到左扫 [ql,qr]：返回 sum w_j * min(该点右侧部分的最小 c, ctx)，
// 并把 ctx 更新为已扫过部分的最小 c。右侧必须先算，故拆成两条语句。
ll rangePsi(int p, int l, int r, int ql, int qr, ll &ctx) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) {
        ll res = queryCap(p, l, r, ctx);
        if (tmn[p] < ctx) ctx = tmn[p];
        return res;
    }
    int mid = (l + r) >> 1;
    ll res = rangePsi(p << 1 | 1, mid + 1, r, ql, qr, ctx);
    res += rangePsi(p << 1, l, mid, ql, qr, ctx);
    return res;
}

// Sum(A,x) = sum_{a=1}^{A} min(Q(a), x)
ll resultQuery(ll A, ll x) {
    if (A < 1) return 0;
    if (A > vs[m] - 1) A = vs[m] - 1;   // 右侧 j>k 的段用 S 一次算完
    int k = (int)(upper_bound(vs + 1, vs + 1 + m, A) - (vs + 1));  // v_j <= A 的个数
    if (k == 0) return A * min(tmn[1], x);
    ll pw = A - vs[k] + 1;                                   // 第 k+1 段被截断的长度
    ll S = (k + 1 <= m) ? rangeMin(1, 1, m, k + 1, m) : INF; // 右侧激活部分最小值
    ll ctx = min(S, x);
    ll res = rangePsi(1, 1, m, 1, k, ctx);
    res += pw * min(S, x);
    return res;
}

// 当前 U 对应的 g(U)，结果对 MOD 取模
ll gValue() {
    if (tmn[1] >= INF) return MX % MOD * ((MX - 1) % MOD) % MOD * ((MOD + 1) / 2) % MOD; // C(M,2)
    int p = 1, l = 1, r = m;
    while (l < r) {                                  // 找最右的激活叶（得 L）
        int mid = (l + r) >> 1;
        if (tmn[p << 1 | 1] < INF) { p = p << 1 | 1; l = mid + 1; }
        else { p = p << 1; r = mid; }
    }
    ll Lv = vs[l], Rv = tmn[1];
    ll A = min(Rv, Lv - 1);
    __int128 H = 0;
    if (A >= 1) H = resultQuery(A, INF) - resultQuery(A, Lv - 1);
    __int128 E = 0;
    if (Rv >= Lv) E = sumB(MX - Rv, MX - Lv);
    return (ll)((H + E) % MOD);
}

void insertRect(int i) {
    int g = gid[i];
    ms[g].insert(rx2[i]);
    update(1, 1, m, g, *ms[g].begin());
}

void removeRect(int i) {
    int g = gid[i];
    ms[g].erase(ms[g].find(rx2[i]));
    update(1, 1, m, g, ms[g].empty() ? INF : *ms[g].begin());
}

// 第二部分总贡献：所有 h 的 g(U_h) 之和
ll case2() {
    // 离散化 x1
    for (int i = 0; i < n; ++i) vs[i + 1] = rx1[i];
    sort(vs + 1, vs + 1 + n);
    m = (int)(unique(vs + 1, vs + 1 + n) - (vs + 1));
    for (int i = 0; i < n; ++i) {
        gid[i] = (int)(lower_bound(vs + 1, vs + 1 + m, rx1[i]) - vs);
        ms[gid[i]].clear();
    }
    build(1, 1, m);

    // 事件：h=1 先插入 y1>=2 的；h=y1 删除；h=y2+1 插入
    ev.clear();
    for (int i = 0; i < n; ++i) {
        if (ry1[i] >= 2) ev.push_back(make_pair(1, i + 1));
        if (ry2[i] + 1 <= MX) ev.push_back(make_pair(ry2[i] + 1, i + 1));
        if (ry1[i] >= 2) ev.push_back(make_pair(ry1[i], -(i + 1)));
    }
    sort(ev.begin(), ev.end());

    ll res = 0;
    ll cur = 1;      // 当前已经算过的 h 区间起点
    size_t ptr = 0;
    while (ptr < ev.size()) {
        ll h = ev[ptr].first;
        if (h > cur) {
            res = (res + (h - cur) % MOD * gValue()) % MOD;
            cur = h;
        }
        while (ptr < ev.size() && ev[ptr].first == h) {
            int id = ev[ptr].second;
            if (id > 0) insertRect(id - 1);
            else removeRect(-id - 1);
            ++ptr;
        }
    }
    if (cur <= MX) res = (res + (MX - cur + 1) % MOD * gValue()) % MOD;
    return res;
}

void read_data() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> rx1[i] >> ry1[i] >> rx2[i] >> ry2[i];
        ll ans = (case1() + case2()) % MOD;   // 三条竖线 / 一横两竖
        for (int i = 0; i < n; ++i) {         // 转置后即三条横线 / 一竖两横
            swap(rx1[i], ry1[i]);
            swap(rx2[i], ry2[i]);
        }
        ans = (ans + case1() + case2()) % MOD;
        cout << ans << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    read_data();
    return 0;
}

复杂度

$F_1$ ：排序与断点分块， $O(n\log n)$ 。
$F_2$ ：扫描线 $O(n)$ 个事件，每次单点修改 $O(\log^2 n)$ ； $O(n)$ 次 $\mathrm{Sum}$ 查询，每次 $O(\log n)$ ；均摊 $O(n\log^2 n)$ 。
每组数据对两个方向各做一次，总复杂度 $O(n\log^2 n)$ ，空间 $O(n)$ 。

在 $\sum n\leqslant2\times10^5$ 的约束下可以轻松通过。

总结

这道题的难点不在数据结构，而在把「选三条线」拆成可计数的两类情形。核心步骤有三：

按竖线条数分类，用转置把 $4$ 种方向分布化成两种情形；
在每种情形里固定「中间」的那条线，把其余两条线的约束解成区间长度，于是计数变成对若干断点段的求和；
一横两竖时，未被横线覆盖的矩形构成集合 $U_h$ ，两条竖线的合法对数只依赖 $L,R,Q(a)$ ；用 $(S-c)^+=S-\min(S,c)$ 消去正部，再用「后缀 min + 带权 min 和」的线段树配合 $h$ 的扫描线把 $Q(a)$ 的维护降到 $O(\log n)$ 。

相似的套路（扫描线 + 后缀最小值线段树 + 分类讨论计数）也常出现在区间覆盖计数、矩形并相关的题目中。