PTA 团体程序设计天梯赛 L3-036 血染钟楼 （30/30）（满分）（吉司机线段树）（C++ Java双版本）

九条可怜最近非常沉迷血染钟楼 —— 一款类狼人杀的身份推理类的游戏。在一局血染钟楼的游戏中，玩家们之间隐藏着一名"恶魔"，而所有善良玩家的目标就是将抽到恶魔身份的玩家绳之以法。

今天，九条可怜和她的小伙伴们开了一局 n+1 名玩家参与的游戏，可怜的编号是 0，其他玩家编号从 1 到 n。
可怜抽到的身份是占卜师，其技能如下（注意这儿和标准钟楼规则有出入）：

1. 每个夜晚，你可以选择任意名玩家，并得知被选择的玩家中是否有恶魔。
2. 有一名除你以外善良玩家始终被你的能力视为恶魔。

换句话说，在剩下的 n 名玩家中，存在着两名未知的玩家，如果这两名玩家均未被可怜选中，可怜就会得到信息 0，否则就会得到信息 1。
在抽到身份的时候，可怜就对游戏开始的前 m 个夜晚进行了规划：她打算在第 i 个夜晚选中编号在区间 [li​,ri​] 内的所有玩家。
因为血染钟楼的第一个夜晚通常比较漫长，所以可怜在百无聊赖之际开始了头脑风暴。如果一切顺利，在 m 晚之后，她将能得到 m 个 0 或 1 的信息，共有 2m 种不同的可能性。可怜想要知道在这些可能性中，有多少种结果是可能发生的且可以让她唯一确定被她技能识别的两名玩家。

输入格式：

第一行输入一个整数 t(1≤t≤10^3)，表示数据组数。
第二行输入两个整数 n,m(1≤n,m≤10^5)，表示可怜以外的玩家数量以及可怜规划的夜晚数量。
接下来 m 行每行两个整数 li​,ri​(1≤li​≤ri​≤n)，表示可怜的计划中在第 i 晚会被选中的玩家编号区间。
输入保证所有数据中满足 n>10^3 或 m>10^3 的数据不超过 5 组。

输出格式：

对于每组数据，输出一行一个整数，表示满足条件的可能性数量。答案可能很大，你只需要输出对 998244353 取模后的结果。

输入样例：

3 4 1 2 3 5 4 2 5 1 3 5 5 2 4 10 10 1 2 6 6 3 7 3 6 1 8 9 10 1 6 4 4 8 8 5 8 

输出样例：

1 2 7 

样例解释

在第一组数据中，可怜得到的信息共有两种可能性：

1. 得到的信息为 0，表明两名目标的玩家均不在区间 [2,3] 中，因此可以唯一确定他们的编号为 (1,4)。
2. 得到的信息为 1，表明至少有一名目标的玩家在区间 [2,3] 中，此时共有四种可能性 (1,2),(1,3),(2,4),(3,4)，因此不能唯一确定。
   在第二组数据中，满足要求的两种可能性如下所示：
3. 四天得到的信息依次为 1110，此时目标玩家的编号一定为 (1,5)。
4. 四天得到的信息依次为 1011，此时目标玩家的编号一定为 (4,5)。
   容易验证其他 14 种可能性均不满足条件。

代码长度限制

16 KB

时间限制

6000 ms

内存限制

64 MB

栈限制

8192 KB

Java（30/30）：

import java.io.*; import java.util.*; public class Main { static final int MOD = 998244353, N = 100005, INF = 1_000_000_007; // 只用 3 个 4N 线段树数组, 全程复用 static int[] v1 = new int[N << 2], v2 = new int[N << 2], lzB = new int[N << 2]; static int[] minR = new int[N], maxL = new int[N]; static int[] yl = new int[N], xl = new int[N]; static int[] L = new int[N], R = new int[N], stk = new int[N]; static int[] hL = new int[N + 2], nL = new int[N], hR = new int[N + 2], nR = new int[N]; static int[] c1x = new int[N], c1y = new int[N]; static int c1n; static long[] c1e = new long[N]; static int[] iHead = new int[N + 2], iNxt = new int[N], iVal = new int[N]; static int iTot; static int[] bit = new int[N + 1]; static int[] idx = new int[N], tmp = new int[N]; static int[] headC = new int[N + 2], nxtC = new int[N + 2]; // 桶排序专用 static int spIv, spxIv; // ========== Fast I/O ========== static InputStream in = System.in; static byte[] inbuf = new byte[1 << 16]; static int lenbuf = 0, ptrbuf = 0; static int readByte() { if (lenbuf == -1) throw new InputMismatchException(); if (ptrbuf >= lenbuf) { ptrbuf = 0; try { lenbuf = in.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if (lenbuf <= 0) return -1; } return inbuf[ptrbuf++]; } static int ni() { int num = 0, b; boolean minus = false; while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if (b == -1) return -1; if (b == '-') { minus = true; b = readByte(); } while (true) { if (b >= '0' && b <= '9') num = num * 10 + (b - '0'); else return minus ? -num : num; b = readByte(); } } public static void main(String[] args) throws IOException { int t = ni(); if (t == -1) return; StringBuilder sb = new StringBuilder(); while (t-- > 0) solve(sb); System.out.print(sb); } // ========== STM: 标记永久化 min 树 ========== static void stmBuild(int u, int l, int r, int val) { v1[u] = val; if (l == r) return; int m = l + r >> 1; stmBuild(u<<1, l, m, val); stmBuild(u<<1|1, m+1, r, val); } static void stmUpd(int u, int l, int r, int ql, int qr, int val) { if (ql > r || qr < l) return; if (ql <= l && r <= qr) { v1[u] = v1[u] < val ? v1[u] : val; return; } int m = l + r >> 1; stmUpd(u<<1, l, m, ql, qr, val); stmUpd(u<<1|1, m+1, r, ql, qr, val); } static int stmQry(int u, int l, int r, int p) { if (l == r) return v1[u]; int m = l + r >> 1; int child = p <= m ? stmQry(u<<1, l, m, p) : stmQry(u<<1|1, m+1, r, p); return v1[u] < child ? v1[u] : child; } // ========== STX: 标记永久化 max 树 ========== static void stxBuild(int u, int l, int r, int val) { v2[u] = val; if (l == r) return; int m = l + r >> 1; stxBuild(u<<1, l, m, val); stxBuild(u<<1|1, m+1, r, val); } static void stxUpd(int u, int l, int r, int ql, int qr, int val) { if (ql > r || qr < l) return; if (ql <= l && r <= qr) { v2[u] = v2[u] > val ? v2[u] : val; return; } int m = l + r >> 1; stxUpd(u<<1, l, m, ql, qr, val); stxUpd(u<<1|1, m+1, r, ql, qr, val); } static int stxQry(int u, int l, int r, int p) { if (l == r) return v2[u]; int m = l + r >> 1; int child = p <= m ? stxQry(u<<1, l, m, p) : stxQry(u<<1|1, m+1, r, p); return v2[u] > child ? v2[u] : child; } // ========== SPM: 单点修改 min 树 ========== static void spmBuild(int u, int l, int r, int val) { spIv = val; v1[u] = val; if (l == r) return; int m = l + r >> 1; spmBuild(u<<1, l, m, val); spmBuild(u<<1|1, m+1, r, val); } static void spmUpd(int u, int l, int r, int p, int val) { if (l == r) { v1[u] = v1[u] < val ? v1[u] : val; return; } int m = l + r >> 1; if (p <= m) spmUpd(u<<1, l, m, p, val); else spmUpd(u<<1|1, m+1, r, p, val); v1[u] = v1[u<<1] < v1[u<<1|1] ? v1[u<<1] : v1[u<<1|1]; } static int spmQry(int u, int l, int r, int ql, int qr) { if (ql > r || qr < l) return spIv; if (ql <= l && r <= qr) return v1[u]; int m = l + r >> 1; int left = spmQry(u<<1, l, m, ql, qr), right = spmQry(u<<1|1, m+1, r, ql, qr); return left < right ? left : right; } // ========== SPX: 单点修改 max 树 ========== static void spxBuild(int u, int l, int r, int val) { spxIv = val; v2[u] = val; if (l == r) return; int m = l + r >> 1; spxBuild(u<<1, l, m, val); spxBuild(u<<1|1, m+1, r, val); } static void spxUpd(int u, int l, int r, int p, int val) { if (l == r) { v2[u] = v2[u] > val ? v2[u] : val; return; } int m = l + r >> 1; if (p <= m) spxUpd(u<<1, l, m, p, val); else spxUpd(u<<1|1, m+1, r, p, val); v2[u] = v2[u<<1] > v2[u<<1|1] ? v2[u<<1] : v2[u<<1|1]; } static int spxQry(int u, int l, int r, int ql, int qr) { if (ql > r || qr < l) return spxIv; if (ql <= l && r <= qr) return v2[u]; int m = l + r >> 1; int left = spxQry(u<<1, l, m, ql, qr), right = spxQry(u<<1|1, m+1, r, ql, qr); return left > right ? left : right; } // ========== Cover Tree ========== static void cvPu(int u) { int l = u<<1, r = l|1; if (v1[l] < v1[r]) { v1[u] = v1[l]; v2[u] = v2[l]; } else if (v1[l] > v1[r]) { v1[u] = v1[r]; v2[u] = v2[r]; } else { v1[u] = v1[l]; v2[u] = v2[l] + v2[r]; } } static void cvBuild(int u, int l, int r) { v1[u] = lzB[u] = 0; v2[u] = r - l + 1; if (l == r) return; int m = l + r >> 1; cvBuild(u<<1, l, m); cvBuild(u<<1|1, m+1, r); } static void cvPd(int u) { if (lzB[u] != 0) { int val = lzB[u]; v1[u<<1] += val; lzB[u<<1] += val; v1[u<<1|1] += val; lzB[u<<1|1] += val; lzB[u] = 0; } } static void cvMod(int u, int l, int r, int ql, int qr, int val) { if (ql > r || qr < l) return; if (ql <= l && r <= qr) { v1[u] += val; lzB[u] += val; return; } cvPd(u); int m = l + r >> 1; cvMod(u<<1, l, m, ql, qr, val); cvMod(u<<1|1, m+1, r, ql, qr, val); cvPu(u); } static int cvFk(int u, int l, int r, int k) { if (l == r) return l; cvPd(u); int m = l + r >> 1; int lz = v1[u<<1] == 0 ? v2[u<<1] : 0; return k <= lz ? cvFk(u<<1, l, m, k) : cvFk(u<<1|1, m+1, r, k - lz); } // ========== SegBeats Mode A: chmin + qmax ========== static void baPu(int u) { int l = u<<1, r = l|1; v1[u] = v1[l] > v1[r] ? v1[l] : v1[r]; if (v1[l] == v1[r]) v2[u] = v2[l] > v2[r] ? v2[l] : v2[r]; else if (v1[l] > v1[r]) v2[u] = v2[l] > v1[r] ? v2[l] : v1[r]; else v2[u] = v1[l] > v2[r] ? v1[l] : v2[r]; } static void baBuild(int u, int l, int r, int val) { lzB[u] = INF; v1[u] = val; v2[u] = -1; if (l == r) return; int m = l + r >> 1; baBuild(u<<1, l, m, val); baBuild(u<<1|1, m+1, r, val); } static void baApply(int u, int val) { if (val < v1[u]) { v1[u] = val; lzB[u] = lzB[u] < val ? lzB[u] : val; } } static void baPd(int u) { if (lzB[u] < INF) { baApply(u<<1, lzB[u]); baApply(u<<1|1, lzB[u]); lzB[u] = INF; } } static void baChmin(int u, int l, int r, int ql, int qr, int val) { if (ql > r || qr < l || val >= v1[u]) return; if (ql <= l && r <= qr && val > v2[u]) { baApply(u, val); return; } baPd(u); int m = l + r >> 1; baChmin(u<<1, l, m, ql, qr, val); baChmin(u<<1|1, m+1, r, ql, qr, val); baPu(u); } static int baQmax(int u, int l, int r, int ql, int qr) { if (ql > r || qr < l) return 0; if (ql <= l && r <= qr) return v1[u]; baPd(u); int m = l + r >> 1; int left = baQmax(u<<1, l, m, ql, qr), right = baQmax(u<<1|1, m+1, r, ql, qr); return left > right ? left : right; } // ========== SegBeats Mode B: chmax + qmin ========== static void bbPu(int u) { int l = u<<1, r = l|1; v1[u] = v1[l] < v1[r] ? v1[l] : v1[r]; if (v1[l] == v1[r]) v2[u] = v2[l] < v2[r] ? v2[l] : v2[r]; else if (v1[l] < v1[r]) v2[u] = v2[l] < v1[r] ? v2[l] : v1[r]; else v2[u] = v1[l] < v2[r] ? v1[l] : v2[r]; } static void bbBuild(int u, int l, int r, int val) { lzB[u] = 0; v1[u] = val; v2[u] = INF; if (l == r) return; int m = l + r >> 1; bbBuild(u<<1, l, m, val); bbBuild(u<<1|1, m+1, r, val); } static void bbApply(int u, int val) { if (val > v1[u]) { v1[u] = val; lzB[u] = lzB[u] > val ? lzB[u] : val; } } static void bbPd(int u) { if (lzB[u] > 0) { bbApply(u<<1, lzB[u]); bbApply(u<<1|1, lzB[u]); lzB[u] = 0; } } static void bbChmax(int u, int l, int r, int ql, int qr, int val) { if (ql > r || qr < l || val <= v1[u]) return; if (ql <= l && r <= qr && val < v2[u]) { bbApply(u, val); return; } bbPd(u); int m = l + r >> 1; bbChmax(u<<1, l, m, ql, qr, val); bbChmax(u<<1|1, m+1, r, ql, qr, val); bbPu(u); } static int bbQmin(int u, int l, int r, int ql, int qr) { if (ql > r || qr < l) return INF; if (ql <= l && r <= qr) return v1[u]; bbPd(u); int m = l + r >> 1; int left = bbQmin(u<<1, l, m, ql, qr), right = bbQmin(u<<1|1, m+1, r, ql, qr); return left < right ? left : right; } static void solve(StringBuilder sb) throws IOException { int n = ni(), m = ni(); if (n < 2 || m == 0) { for (int i = 0; i < m; i++) { ni(); ni(); } sb.append(0).append('\n'); return; } Arrays.fill(hL, 0, n + 2, -1); Arrays.fill(hR, 0, n + 2, -1); for (int i = 0; i < m; i++) { L[i] = ni(); R[i] = ni(); nL[i] = hL[L[i]]; hL[L[i]] = i; nR[i] = hR[R[i]]; hR[R[i]] = i; } // 步骤1: minR stmBuild(1, 1, n, n + 1); for (int i = 0; i < m; i++) stmUpd(1, 1, n, L[i], R[i], R[i]); for (int i = 1; i <= n; i++) minR[i] = stmQry(1, 1, n, i); // 步骤2: maxL stxBuild(1, 1, n, 0); for (int i = 0; i < m; i++) stxUpd(1, 1, n, L[i], R[i], L[i]); for (int i = 1; i <= n; i++) maxL[i] = stxQry(1, 1, n, i); // 步骤3: pre->yl[], nex->xl[] int top = 0; for (int x = 1; x <= n; x++) { int res = -1, lo = 0, hi = top - 1; while (lo <= hi) { int md = lo + hi >> 1; if (minR[stk[md]] >= x) { res = stk[md]; lo = md + 1; } else hi = md - 1; } yl[x] = res == -1 ? 0 : res; while (top > 0 && minR[stk[top-1]] <= minR[x]) top--; stk[top++] = x; } top = 0; for (int y = n; y >= 1; y--) { int res = -1, lo = 0, hi = top - 1; while (lo <= hi) { int md = lo + hi >> 1; if (maxL[stk[md]] <= y) { res = stk[md]; lo = md + 1; } else hi = md - 1; } xl[y] = res == -1 ? n + 1 : res; while (top > 0 && maxL[stk[top-1]] >= maxL[y]) top--; stk[top++] = y; } // 步骤4: Case 1 cvBuild(1, 1, n); for (int i = 0; i < m; i++) cvMod(1, 1, n, L[i], R[i], 1); c1n = 0; for (int i = 1; i <= n; i++) { for (int j = hL[i]; j != -1; j = nL[j]) cvMod(1, 1, n, L[j], R[j], -1); if (v1[1] == 0 && v2[1] == 2) { int a = cvFk(1, 1, n, 1), b = cvFk(1, 1, n, 2); if (a > b) { int t2 = a; a = b; b = t2; } if (i == a || i == b) { c1x[c1n] = a; c1y[c1n] = b; c1n++; } } for (int j = hR[i]; j != -1; j = nR[j]) cvMod(1, 1, n, L[j], R[j], 1); } if (c1n > 0) { for (int i = 0; i < c1n; i++) c1e[i] = (long) c1x[i] * N + c1y[i]; Arrays.sort(c1e, 0, c1n); int u = 0; for (int i = 0; i < c1n; i++) if (i == 0 || c1e[i] != c1e[i-1]) c1e[u++] = c1e[i]; c1n = u; for (int i = 0; i < c1n; i++) { c1x[i] = (int)(c1e[i] / N); c1y[i] = (int)(c1e[i] % N); } } // 步骤5: ylim1 (O(N) 桶排按 R 降序) Arrays.fill(headC, 0, n + 2, -1); for (int i = 0; i < m; i++) { int val = R[i]; nxtC[i] = headC[val]; headC[val] = i; } int ptr = 0; for (int val = n; val >= 1; val--) { for (int i = headC[val]; i != -1; i = nxtC[i]) idx[ptr++] = i; } spmBuild(1, 1, n, n + 1); ptr = 0; for (int x = n; x >= 1; x--) { while (ptr < m && R[idx[ptr]] >= x) { int j = idx[ptr++]; spmUpd(1, 1, n, L[j], R[j]); } int b = spmQry(1, 1, n, yl[x] + 1, x); yl[x] = b <= n ? b + 1 : n + 1; } // 步骤6: ylim2 baBuild(1, 1, n, n + 1); for (int x = n; x >= 1; x--) { if (x + 1 <= n) for (int j = hL[x+1]; j != -1; j = nL[j]) baChmin(1, 1, n, L[j], R[j], R[j]); int ylim2; if (minR[x] > n) ylim2 = n + 1; else if (minR[x] == x) ylim2 = x + 1; else { int f = baQmax(1, 1, n, x + 1, minR[x]); ylim2 = f > n ? n + 1 : (f + 1 > minR[x] + 1 ? f + 1 : minR[x] + 1); } yl[x] = yl[x] > ylim2 ? yl[x] : ylim2; } // 步骤7: xlim2 (O(N) 桶排按 L 升序) Arrays.fill(headC, 0, n + 2, -1); for (int i = m - 1; i >= 0; i--) { // 倒序枚举保持相对稳定 int val = L[i]; nxtC[i] = headC[val]; headC[val] = i; } ptr = 0; for (int val = 1; val <= n; val++) { for (int i = headC[val]; i != -1; i = nxtC[i]) idx[ptr++] = i; } spxBuild(1, 1, n, 0); ptr = 0; for (int y = 1; y <= n; y++) { while (ptr < m && L[idx[ptr]] <= y) { int j = idx[ptr++]; spxUpd(1, 1, n, R[j], L[j]); } int b = spxQry(1, 1, n, y, xl[y] - 1); xl[y] = b > 0 ? b - 1 : 0; } // 步骤8: xlim1 bbBuild(1, 1, n, 0); for (int y = 1; y <= n; y++) { if (y >= 2) for (int j = hR[y-1]; j != -1; j = nR[j]) bbChmax(1, 1, n, L[j], R[j], L[j]); int xlim1; if (maxL[y] == 0) xlim1 = 0; else if (maxL[y] == y) xlim1 = y - 1; else { int h = bbQmin(1, 1, n, maxL[y], y - 1); int hCand = h - 1 < maxL[y] - 1 ? h - 1 : maxL[y] - 1; xlim1 = h == 0 ? 0 : hCand; } xl[y] = xl[y] < xlim1 ? xl[y] : xlim1; } // 步骤9: 二维数点 iTot = 0; Arrays.fill(iHead, 0, n + 2, -1); for (int x = 1; x <= n; x++) { if (yl[x] >= 1 && yl[x] <= n) { iNxt[iTot] = iHead[yl[x]]; iVal[iTot] = x; iHead[yl[x]] = iTot++; } } Arrays.fill(bit, 0, n + 2, 0); long ans = 0; for (int y = 1; y <= n; y++) { for (int p = iHead[y]; p != -1; p = iNxt[p]) for (int k = iVal[p]; k <= n; k += k & -k) bit[k]++; int ub = xl[y] < y - 1 ? xl[y] : y - 1; if (ub >= 1) { int s = 0; for (int k = ub; k > 0; k -= k & -k) s += bit[k]; ans += s; } } for (int i = 0; i < c1n; i++) if (!(c1y[i] >= yl[c1x[i]] && c1x[i] <= xl[c1y[i]])) ans++; sb.append(ans % MOD).append('\n'); } }

cpp（25/30）:

/* * 血染钟楼 * 内存：O(n²) 个 ull 值，每个 8 字节 * n=2000 时约 16MB */ #include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; mt19937_64 rng(42); void solve() { int n, m; scanf("%d%d", &n, &m); vector<int> sl(m), sr(m); for (int i = 0; i < m; i++) scanf("%d%d", &sl[i], &sr[i]); if (n < 2 || m == 0) { printf("0\n"); return; } vector<ull> w(m); for (int i = 0; i < m; i++) w[i] = rng(); // h(x) = 覆盖 x 的区间权值和 vector<ull> h(n+2, 0); for (int j = 0; j < m; j++) { h[sl[j]] += w[j]; h[sr[j]+1] -= w[j]; } for (int i = 1; i <= n; i++) h[i] += h[i-1]; // 按左端点分组 vector<vector<pair<int,int>>> byL(n+2); for (int j = 0; j < m; j++) byL[sl[j]].push_back({sr[j], j}); // delta[r] = Σ w_j for [l_j <= x AND r_j == r] vector<ull> d(n+2, 0); // 存储所有 H 值 vector<ull> hvec; hvec.reserve((long long)n * (n-1) / 2); for (int x = 1; x <= n; x++) { for (auto [r, j] : byL[x]) d[r] += w[j]; ull g = 0; for (int y = n; y > x; y--) { g += d[y]; hvec.push_back(h[x] + h[y] - g); } } sort(hvec.begin(), hvec.end()); long long ans = 0; int sz = hvec.size(); for (int i = 0; i < sz; ) { int j = i; while (j < sz && hvec[j] == hvec[i]) j++; if (j - i == 1) ans++; i = j; } printf("%lld\n", ans % 998244353); } int main() { int t; scanf("%d", &t); while (t--) solve(); return 0; } 

2026.02.15 更新AC算法  （30/30）：

相关知识点：https://oi-wiki.org/ds/seg-beats/（吉司机线段树）

应该也是这道题全网第一份公开的AC代码，读了好几遍吉老师的解题报告，终于啃下来了。

【题意简述】

给定 n 个位置和 m 个区间 [L_i, R_i]，求有多少个无序对 (x, y)（x < y）满足：
去掉所有包含 x 或包含 y 的区间后，剩余区间仍然覆盖 [1, n] 中除 x, y 以外的所有位置。
答案对 998244353 取模。

一个合法对 (x, y) 需要满足：每个区间要么不包含 x 也不包含 y，
要么可以被牺牲掉而不影响其余位置的覆盖。

将问题分为两类讨论：

  Case 1：特殊对（退化情况）
    存在某个位置 i，使得去掉所有左端点恰好为 i 的区间后，恰好有 2 个位置未被覆盖（记为 a < b），且 i ∈ {a, b}。
    这类点对的特征是：所有覆盖 x 或 y 的区间都"经过"同一个关键点，
    去掉这些区间后恰好只暴露出 x 和 y。

  Case 2：一般情况（二维数点）
    对于一般的合法对 (x, y)，可以为每个 x 算出 y 的下界 ylim[x]，为每个 y 算出 x 的上界 xlim[y]。合法条件为：
      x < y,  y >= ylim[x],  x <= xlim[y]
    这是一个经典的二维数点问题，可以用 BIT 扫描线解决。

最终答案 = Case 2 数点结果 + Case 1 中不被 Case 2 覆盖的特殊对数量。

一、预处理

对每个位置定义两个关键量：
  - minRight[x]：所有覆盖位置 x 的区间中，最小的右端点。
  - maxLeft[y]：所有覆盖位置 y 的区间中，最大的左端点。

用标记永久化线段树（区间推 min/max 标记 + 单点查询）在 O(m log n) 内完成。

直觉：minRight[x] 表示"从 x 出发，覆盖 x 的区间最短能延伸到哪里"。
如果 y > minRight[x]，则存在一个覆盖 x 的区间 [l, minRight[x]] 不覆盖 y，
这个区间不需要被去掉。

二、pre 和 nex

  - pre[x]：[1, x-1] 中最右的位置 p，使得 minRight[p] >= x。
  - nex[y]：[y+1, n] 中最左的位置 q，使得 maxLeft[q] <= y。

含义：pre[x] 是 x 左边最远的、与 x 纠缠 的位置——它被某个区间覆盖，而该区间的右端点至少延伸到 x，
因此去掉覆盖 x 的区间时可能影响到 p。nex[y] 对称。

实现：用线段树二分。
  segPre 叶子存 minR[x]，维护区间 max，查询 [1, x-1] 中最右的满足 minR[p] >= x 的 p。
  segNex 对称。

三、Case 1 实现

用一棵支持 区间加、全局最小值计数、第 k 个零位置查询 的线段树。

1. 先把所有区间加入（每个区间对 [L_i, R_i] 做 +1）。
2. 从左到右扫描位置 i：
   - 扣除所有 L_j = i 的区间（做 -1）。
   - 如果此时恰好有 2 个零点 a < b，且 i ∈ {a, b}，
     则 (a, b) 是 Case 1 候选对。
   - 加回所有 R_j = i 的区间（做 +1）。
3. 对候选对编码去重（同一对可能被 i=a 和 i=b 各枚举一次）。

复杂度：每个区间恰好被加入和删除各一次，
总共 O(m) 次区间操作，每次 O(log n)。

四、Case 2：ylim 和 xlim 的计算

ylim[x] = max(ylim1[x], ylim2[x])

  ylim1[x]：在 [pre[x]+1, x] 范围内，所有覆盖区间的最小 R 值加 1。

    含义：[pre[x]+1, x] 是 x 左侧"与 x 纠缠"的区域。
    这些位置被覆盖它们的区间保护，但如果某个区间的右端点 R 很小
    （即 R < y），那么这个区间不覆盖 y，不需要去掉。
    最小的那个 R 决定了 y 至少要多大才能避免冲突。

    实现：按 R 降序扫描 x（从右到左），
    用 segPtMin（单点修改、区间查 min）维护。
    每次把 R >= x 的区间插入，查询 [pre[x]+1, x] 的 min。

  ylim2[x]：[x+1, minRight[x]] 的"桥梁连通性"约束。

    含义：从 x 到 minRight[x] 之间的位置需要被"桥梁区间"
    （不覆盖 x 的区间）连续覆盖。如果中间有断点，y 必须跳过断点。
    具体地，如果桥梁区间在某处断裂（最大的断裂右端点为 f），
    则 y 至少要 >= max(f+1, minR[x]+1)。

    实现：用 Segment Tree Beats（segBtMin，区间 chmin + 查 max），
    从右到左扫描 x，逐步加入左端点为 x+1 的区间。

xlim[y] = min(xlim1[y], xlim2[y])

  与 ylim 完全对称：
  - xlim2[y]：在 [y, nex[y]-1] 范围内，所有覆盖区间的最大 L 值减 1。
  - xlim1[y]：[maxLeft[y], y-1] 的桥梁连通性约束
    （SegBeats 区间 chmax + 查 min）。

五、二维数点

最终合法条件：x < y, y >= ylim[x], x <= xlim[y]。

这是一个标准的二维偏序计数问题：
1. 对每个 x，在 y = ylim[x] 时刻将 x 加入 BIT。
2. 从小到大扫描 y，查询 BIT 中 [1, min(xlim[y], y-1)] 的前缀和。

最后加上 Case 1 中不满足 Case 2 条件的特殊对。
 

做法分两个 Case：
Case1:

去掉所有经过 x 的区间后，恰好只剩 x 和另一个点 y 未被覆盖，
且 x, y 满足特殊的"互为关键点"关系。用扫描线 + 线段树计数零点。

Case2:

对每个 x 算出 ylim[x]（y 的下界），对每个 y 算出 xlim[y]（x 的上界），
转化为二维数点：统计满足 y >= ylim[x] 且 x <= xlim[y] 且 x < y 的对数。

用 BIT 扫描线完成。

六、复杂度

  时间：O((n + m) log n) 每棵线段树的操作均为 O(log n)，
  SegBeats 均摊 O(log^2 n) 但实际表现接近 O(log n)。
  空间：O(n)（多棵线段树各 4n 节点）。

关键数组含义：
minRight[x]: 所有覆盖 x 的区间中，右端点的最小值（即最"紧"的右边界）
maxLeft[y]: 所有覆盖 y 的区间中，左端点的最大值（即最"紧"的左边界）
pre[x]:  x 左边最靠右的位置 p，使得存在区间 [L,R] 满足 L<=p 且 R>=x
（即 p 和 x 被同一个区间覆盖，p 是最右的这样的点）
nex[y]:  y 右边最靠左的位置 q，使得存在区间 [L,R] 满足 L<=y 且 R>=q
ylim[x]: x 作为左端时，y 的最小合法值
xlim[y]: y 作为右端时，x 的最大合法值

// 血染钟楼 L3-036 #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,popcnt") #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 998244353, N = 100005, INF = 1e9 + 7; namespace IO { const int SZ = 1 << 20; char ib[SZ], *ip = ib, *ie = ib, ob[SZ]; int op = 0; inline char gc() { return ip == ie && (ie = (ip = ib) + fread(ib, 1, SZ, stdin), ip == ie) ? EOF : *ip++; } inline int readInt() { int x = 0; char c = gc(); while (c < '0' || c > '9') c = gc(); while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = gc(); } return x; } inline void putChar(char c) { if (op == SZ) { fwrite(ob, 1, SZ, stdout); op = 0; } ob[op++] = c; } inline void write(ll x) { if (x == 0) { putChar('0'); return; } static int sta[35]; int top = 0; while (x) { sta[top++] = x % 10; x /= 10; } while (top) putChar(sta[--top] + '0'); } inline void flush() { fwrite(ob, 1, op, stdout); op = 0; } } using IO::readInt; using IO::write; using IO::putChar; using IO::flush; struct MinOp { static inline __attribute__((always_inline)) int op(int a, int b) { return a < b ? a : b; } }; struct MaxOp { static inline __attribute__((always_inline)) int op(int a, int b) { return a > b ? a : b; } }; template<class Op> struct ZKW_RUPQ { int zB, init_val; int seg[N << 2]; void build(int n, int v) { init_val = v; zB = 1; while (zB <= n) zB <<= 1; if (v == 0) memset(seg, 0, sizeof(int) * 2 * zB); else fill(seg, seg + 2 * zB, v); } void upd(int ql, int qr, int v) { for (int l = ql - 1 + zB, r = qr + 1 + zB; l ^ r ^ 1; l >>= 1, r >>= 1) { if (~l & 1) seg[l ^ 1] = Op::op(seg[l ^ 1], v); if (r & 1) seg[r ^ 1] = Op::op(seg[r ^ 1], v); } } void push_all_to_leaves() { for (int i = 1; i < zB; i++) { seg[i << 1] = Op::op(seg[i << 1], seg[i]); seg[i << 1 | 1] = Op::op(seg[i << 1 | 1], seg[i]); } } inline int get_leaf(int i) { return seg[i + zB]; } }; template<class Op> struct ZKW_PURQ { int zB, init_val; int seg[N << 2]; void build(int n, int v) { init_val = v; zB = 1; while (zB <= n) zB <<= 1; if (v == 0) memset(seg, 0, sizeof(int) * 2 * zB); else fill(seg, seg + 2 * zB, v); } void upd(int p, int v) { int i = p + zB; seg[i] = Op::op(seg[i], v); for (i >>= 1; i; i >>= 1) seg[i] = Op::op(seg[i << 1], seg[i << 1 | 1]); } inline int qry(int ql, int qr) { int res = init_val; for (int l = ql - 1 + zB, r = qr + 1 + zB; l ^ r ^ 1; l >>= 1, r >>= 1) { if (~l & 1) res = Op::op(res, seg[l ^ 1]); if (r & 1) res = Op::op(res, seg[r ^ 1]); } return res; } }; const int BK = 256; template<class UOp, class QOp> struct BlockSolver { int bn, ULazyInit, QInit; int bval[N], bagg[N / BK + 10], blazy[N / BK + 10]; void init(int n, int vInit, int aggInit, int uLzInit, int qInit) { bn = n; ULazyInit = uLzInit; QInit = qInit; int bc = (n - 1) / BK + 1; if (vInit == 0) memset(bval, 0, sizeof(int) * (n + 1)); else fill(bval, bval + n + 1, vInit); if (aggInit == 0) memset(bagg, 0, sizeof(int) * bc); else fill(bagg, bagg + bc, aggInit); if (uLzInit == 0) memset(blazy, 0, sizeof(int) * bc); else fill(blazy, blazy + bc, uLzInit); } inline void scatter(int b, int ql, int qr, int v) { int l = b * BK + 1, r = min((b + 1) * BK, bn); int lz = blazy[b]; if (lz != ULazyInit) { #pragma GCC ivdep #pragma GCC unroll 8 for (int i = l; i <= r; i++) bval[i] = UOp::op(bval[i], lz); blazy[b] = ULazyInit; } #pragma GCC ivdep for (int i = ql; i <= qr; i++) bval[i] = UOp::op(bval[i], v); int mx = QInit; #pragma GCC ivdep for (int i = l; i <= r; i++) mx = QOp::op(mx, bval[i]); bagg[b] = mx; } void upd(int ql, int qr, int v) { if (ql > qr) return; int lb = (ql - 1) / BK, rb = (qr - 1) / BK; if (lb == rb) { scatter(lb, ql, qr, v); return; } scatter(lb, ql, (lb + 1) * BK, v); for (int b = lb + 1; b < rb; b++) { if (UOp::op(bagg[b], v) == bagg[b]) continue; blazy[b] = UOp::op(blazy[b], v); bagg[b] = v; } scatter(rb, rb * BK + 1, qr, v); } int qry(int ql, int qr) { if (ql > qr) return QInit; int lb = (ql - 1) / BK, rb = (qr - 1) / BK, res = QInit; if (lb == rb) { int lz = blazy[lb]; for (int i = ql; i <= qr; i++) res = QOp::op(res, UOp::op(bval[i], lz)); } else { int lz = blazy[lb]; for (int i = ql, e = (lb + 1) * BK; i <= e; i++) res = QOp::op(res, UOp::op(bval[i], lz)); for (int b = lb + 1; b < rb; b++) res = QOp::op(res, bagg[b]); lz = blazy[rb]; for (int i = rb * BK + 1; i <= qr; i++) res = QOp::op(res, UOp::op(bval[i], lz)); } return res; } }; struct CoverTree { int seg[N << 2], seg2[N << 2], blz[N << 2]; inline void push_up(int u) { int ls = u << 1, rs = ls | 1; int sl = seg[ls], sr = seg[rs]; if (sl < sr) { seg[u] = sl; seg2[u] = seg2[ls]; } else if (sl > sr) { seg[u] = sr; seg2[u] = seg2[rs]; } else { seg[u] = sl; seg2[u] = seg2[ls] + seg2[rs]; } } inline void push_down(int u) { int lz = blz[u]; if (lz) { int ls = u << 1, rs = ls | 1; seg[ls] += lz; blz[ls] += lz; seg[rs] += lz; blz[rs] += lz; blz[u] = 0; } } void build(int u, int l, int r) { seg[u] = blz[u] = 0; seg2[u] = r - l + 1; if (l == r) return; int m = (l + r) >> 1; build(u << 1, l, m); build(u << 1 | 1, m + 1, r); } void upd(int u, int l, int r, int ql, int qr, int v) { if (ql <= l && r <= qr) { seg[u] += v; blz[u] += v; return; } push_down(u); int m = (l + r) >> 1; int ls = u << 1, rs = ls | 1; if (ql <= m) upd(ls, l, m, ql, qr, v); if (qr > m) upd(rs, m + 1, r, ql, qr, v); push_up(u); } int find_k(int u, int l, int r, int k) { while (l < r) { push_down(u); int m = (l + r) >> 1; int ls = u << 1; int lz = (seg[ls] == 0) ? seg2[ls] : 0; if (k <= lz) { u = ls; r = m; } else { u = ls | 1; l = m + 1; k -= lz; } } return l; } }; struct BIT { int bit[N]; void init(int n) { memset(bit, 0, sizeof(int) * (n + 1)); } inline __attribute__((always_inline)) void add(int i, int n) { for (; i <= n; i += i & -i) bit[i]++; } inline __attribute__((always_inline)) int query(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; } }; ZKW_RUPQ<MinOp> stm; ZKW_RUPQ<MaxOp> stx; ZKW_PURQ<MinOp> spm; ZKW_PURQ<MaxOp> spx; CoverTree cvTree; BlockSolver<MinOp, MaxOp> bkMn; BlockSolver<MaxOp, MinOp> bkMx; BIT fen; int minR[N], maxL[N], pre[N], nex_[N]; int ylim[N], xlim[N]; int L[N], R[N], stk[N], sidx[N]; int hL[N], nL[N], hR[N], nR[N]; int c1x[N], c1y[N], c1cnt; ll c1enc[N]; int insH[N], insN[N], insV[N], insT; void csort(int* idx, int len, int* key, int maxv, bool asc) { static int cnt[N], buf[N]; memset(cnt, 0, sizeof(int) * (maxv + 1)); for (int i = 0; i < len; i++) cnt[key[idx[i]]]++; if (asc) { for (int i = 1; i <= maxv; i++) cnt[i] += cnt[i - 1]; for (int i = len - 1; i >= 0; i--) buf[--cnt[key[idx[i]]]] = idx[i]; } else { for (int i = maxv - 1; i >= 0; i--) cnt[i] += cnt[i + 1]; for (int i = len - 1; i >= 0; i--) buf[--cnt[key[idx[i]]]] = idx[i]; } memcpy(idx, buf, sizeof(int) * len); } void solve() { int n = readInt(), m = readInt(); if (n < 2 || m == 0) { for (int i = 0; i < m; i++) { readInt(); readInt(); } write(0); putChar('\n'); return; } for (int i = 1; i <= n + 1; i++) hL[i] = hR[i] = -1; for (int i = 0; i < m; i++) { L[i] = readInt(); R[i] = readInt(); nL[i] = hL[L[i]]; hL[L[i]] = i; nR[i] = hR[R[i]]; hR[R[i]] = i; } stm.build(n, n + 1); for (int i = 0; i < m; i++) stm.upd(L[i], R[i], R[i]); stm.push_all_to_leaves(); for (int i = 1; i <= n; i++) minR[i] = stm.get_leaf(i); stx.build(n, 0); for (int i = 0; i < m; i++) stx.upd(L[i], R[i], L[i]); stx.push_all_to_leaves(); for (int i = 1; i <= n; i++) maxL[i] = stx.get_leaf(i); int stp = 0; for (int x = 1; x <= n; x++) { int res = -1, lo = 0, hi = stp - 1; while (lo <= hi) { int md = (lo + hi) >> 1; if (minR[stk[md]] >= x) { res = stk[md]; lo = md + 1; } else hi = md - 1; } pre[x] = (res == -1) ? 0 : res; while (stp > 0 && minR[stk[stp - 1]] <= minR[x]) stp--; stk[stp++] = x; } stp = 0; for (int y = n; y >= 1; y--) { int res = -1, lo = 0, hi = stp - 1; while (lo <= hi) { int md = (lo + hi) >> 1; if (maxL[stk[md]] <= y) { res = stk[md]; lo = md + 1; } else hi = md - 1; } nex_[y] = (res == -1) ? n + 1 : res; while (stp > 0 && maxL[stk[stp - 1]] >= maxL[y]) stp--; stk[stp++] = y; } cvTree.build(1, 1, n); for (int i = 0; i < m; i++) cvTree.upd(1, 1, n, L[i], R[i], 1); c1cnt = 0; for (int i = 1; i <= n; i++) { for (int j = hL[i]; j != -1; j = nL[j]) cvTree.upd(1, 1, n, L[j], R[j], -1); if (cvTree.seg[1] == 0 && cvTree.seg2[1] == 2) { int a = cvTree.find_k(1, 1, n, 1), b = cvTree.find_k(1, 1, n, 2); if (a > b) swap(a, b); if (i == a || i == b) { c1x[c1cnt] = a; c1y[c1cnt] = b; c1cnt++; } } for (int j = hR[i]; j != -1; j = nR[j]) cvTree.upd(1, 1, n, L[j], R[j], 1); } for (int i = 0; i < c1cnt; i++) c1enc[i] = (ll)c1x[i] * N + c1y[i]; sort(c1enc, c1enc + c1cnt); c1cnt = (int)(unique(c1enc, c1enc + c1cnt) - c1enc); for (int i = 0; i < c1cnt; i++) { c1x[i] = (int)(c1enc[i] / N); c1y[i] = (int)(c1enc[i] % N); } iota(sidx, sidx + m, 0); csort(sidx, m, R, n, false); spm.build(n + 1, n + 1); bkMn.init(n, n + 1, n + 1, INF, 0); int ptr = 0; for (int x = n; x >= 1; x--) { while (ptr < m && R[sidx[ptr]] >= x) { int j = sidx[ptr++]; spm.upd(L[j], R[j]); } if (x + 1 <= n) for (int j = hL[x + 1]; j != -1; j = nL[j]) bkMn.upd(L[j], R[j], R[j]); int b1 = spm.qry(pre[x] + 1, x); int y1 = (b1 <= n) ? b1 + 1 : n + 1; int y2; if (y1 >= n + 1 || minR[x] > n) y2 = n + 1; else if (minR[x] == x) y2 = x + 1; else { int f = bkMn.qry(x + 1, minR[x]); y2 = (f > n) ? n + 1 : max(f + 1, minR[x] + 1); } ylim[x] = max(y1, y2); } iota(sidx, sidx + m, 0); csort(sidx, m, L, n, true); spx.build(n + 1, 0); bkMx.init(n, 0, 0, 0, INF); ptr = 0; for (int y = 1; y <= n; y++) { while (ptr < m && L[sidx[ptr]] <= y) { int j = sidx[ptr++]; spx.upd(R[j], L[j]); } if (y >= 2) for (int j = hR[y - 1]; j != -1; j = nR[j]) bkMx.upd(L[j], R[j], L[j]); int b2 = spx.qry(y, nex_[y] - 1); int x2 = (b2 > 0) ? b2 - 1 : 0; int x1; if (x2 <= 0 || maxL[y] == 0) x1 = 0; else if (maxL[y] == y) x1 = y - 1; else { int h = bkMx.qry(maxL[y], y - 1); x1 = (h == 0) ? 0 : min(h - 1, maxL[y] - 1); } xlim[y] = min(x2, x1); } insT = 0; for (int i = 1; i <= n + 1; i++) insH[i] = -1; for (int x = 1; x <= n; x++) { if (ylim[x] >= 1 && ylim[x] <= n) { insN[insT] = insH[ylim[x]]; insV[insT] = x; insH[ylim[x]] = insT++; } } fen.init(n); ll ans = 0; for (int y = 1; y <= n; y++) { for (int p = insH[y]; p != -1; p = insN[p]) fen.add(insV[p], n); int ub = min(xlim[y], y - 1); if (ub >= 1) ans += fen.query(ub); } for (int i = 0; i < c1cnt; i++) { int x = c1x[i], y = c1y[i]; if (!(y >= ylim[x] && x <= xlim[y])) ans++; } write(ans % MOD); putChar('\n'); } int main() { int t = readInt(); while (t--) solve(); flush(); return 0; }

// 血染钟楼 L3-036 — 吉司机线段树版 #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,popcnt") #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 998244353, N = 100005, INF = 1e9 + 7; // ================= 快读快写 ================= namespace IO { const int SZ = 1 << 20; char ib[SZ], *ip = ib, *ie = ib, ob[SZ]; int op = 0; inline char getChar() { return ip == ie && (ie = (ip = ib) + fread(ib, 1, SZ, stdin), ip == ie) ? EOF : *ip++; } inline int readInt() { int x = 0; char c = getChar(); while (c < '0' || c > '9') c = getChar(); while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getChar(); } return x; } inline void putChar(char c) { if (op == SZ) { fwrite(ob, 1, SZ, stdout); op = 0; } ob[op++] = c; } inline void write(ll x) { if (x > 9) write(x / 10); putChar(x % 10 + '0'); } inline void flush() { fwrite(ob, 1, op, stdout); op = 0; } } using IO::readInt; using IO::write; using IO::putChar; using IO::flush; // ================= 泛型比较函数对象 ================= template<typename T> struct MinOp { const T id = INF; T operator()(T a, T b) const { return min(a, b); } }; template<typename T> struct MaxOp { const T id = 0; T operator()(T a, T b) const { return max(a, b); } }; // ================= 标记永久化线段树 ================= template <typename T, typename Op> struct SegTreeTag { T t[N << 2]; Op op; void build(int u, int l, int r, T init_val) { t[u] = init_val; if (l == r) return; int m = (l + r) >> 1; build(u<<1, l, m, init_val); build(u<<1|1, m+1, r, init_val); } void update(int u, int l, int r, int ql, int qr, T v) { if (ql > r || qr < l) return; if (ql <= l && r <= qr) { t[u] = op(t[u], v); return; } int m = (l + r) >> 1; update(u<<1, l, m, ql, qr, v); update(u<<1|1, m+1, r, ql, qr, v); } T query(int u, int l, int r, int p) { if (l == r) return t[u]; int m = (l + r) >> 1; return op(t[u], p <= m ? query(u<<1, l, m, p) : query(u<<1|1, m+1, r, p)); } }; // ================= 单点修改 + 区间查询线段树 ================= template <typename T, typename Op> struct SegTreePt { T t[N << 2]; Op op; T init_v; void build(int u, int l, int r, T iv) { t[u] = init_v = iv; if (l == r) return; int m = (l + r) >> 1; build(u<<1, l, m, iv); build(u<<1|1, m+1, r, iv); } void update(int u, int l, int r, int p, T v) { if (l == r) { t[u] = op(t[u], v); return; } int m = (l + r) >> 1; if (p <= m) update(u<<1, l, m, p, v); else update(u<<1|1, m+1, r, p, v); t[u] = op(t[u<<1], t[u<<1|1]); } T query(int u, int l, int r, int ql, int qr) { if (ql > r || qr < l) return init_v; if (ql <= l && r <= qr) return t[u]; int m = (l + r) >> 1; return op(query(u<<1, l, m, ql, qr), query(u<<1|1, m+1, r, ql, qr)); } }; // ================= 覆盖计数线段树 (Case 1 扫描线) ================= struct SegTreeCov { int mn[N << 2], cnt[N << 2], lazy[N << 2]; inline void push_up(int u) { int lc = u<<1, rc = u<<1|1; if (mn[lc] < mn[rc]) { mn[u] = mn[lc]; cnt[u] = cnt[lc]; } else if (mn[lc] > mn[rc]) { mn[u] = mn[rc]; cnt[u] = cnt[rc]; } else { mn[u] = mn[lc]; cnt[u] = cnt[lc] + cnt[rc]; } } void build(int u, int l, int r) { mn[u] = lazy[u] = 0; cnt[u] = r - l + 1; if (l == r) return; int m = (l + r) >> 1; build(u<<1, l, m); build(u<<1|1, m+1, r); } inline void apply(int u, int v) { mn[u] += v; lazy[u] += v; } inline void push_down(int u) { if (lazy[u]) { apply(u<<1, lazy[u]); apply(u<<1|1, lazy[u]); lazy[u] = 0; } } void modify(int u, int l, int r, int ql, int qr, int v) { if (ql > r || qr < l) return; if (ql <= l && r <= qr) { apply(u, v); return; } push_down(u); int m = (l + r) >> 1; modify(u<<1, l, m, ql, qr, v); modify(u<<1|1, m+1, r, ql, qr, v); push_up(u); } int findKthZero(int u, int l, int r, int k) { if (l == r) return l; push_down(u); int m = (l + r) >> 1; int leftZeros = (mn[u<<1] == 0 ? cnt[u<<1] : 0); if (k <= leftZeros) return findKthZero(u<<1, l, m, k); return findKthZero(u<<1|1, m+1, r, k - leftZeros); } } coverTree; // ================= 吉司机线段树 (Segment Tree Beats) ================= // 复用同一组数组, 提供两套操作: // Mode A (ylim2): 区间 chmin + 区间 query max // Mode B (xlim1): 区间 chmax + 区间 query min // 两个 Phase 不同时使用, 每次 build 重置 struct SegBeats { // mx/mx2: 最大值/严格次大值 (Mode A 用) // mn/mn2: 最小值/严格次小值 (Mode B 用) // lazy: chmin 或 chmax 的懒标记 int mx[N << 2], mx2[N << 2]; // Mode A int mn[N << 2], mn2[N << 2]; // Mode B int lazy[N << 2]; // ---- Mode A: chmin + qmax ---- inline void pullA(int u) { int lc = u<<1, rc = u<<1|1; mx[u] = max(mx[lc], mx[rc]); if (mx[lc] == mx[rc]) mx2[u] = max(mx2[lc], mx2[rc]); else if (mx[lc] > mx[rc]) mx2[u] = max(mx2[lc], mx[rc]); else mx2[u] = max(mx[lc], mx2[rc]); } void buildA(int u, int l, int r, int v) { lazy[u] = INF; // chmin 的无效标记 mx[u] = v; mx2[u] = -1; if (l == r) return; int m = (l + r) >> 1; buildA(u<<1, l, m, v); buildA(u<<1|1, m+1, r, v); } // 对节点 u 施加 chmin(v), 前提: mx2[u] < v < mx[u] inline void applyChmin(int u, int v) { mx[u] = v; lazy[u] = min(lazy[u], v); } inline void pushA(int u) { if (lazy[u] < INF) { for (int c : {u<<1, u<<1|1}) if (mx[c] > lazy[u]) applyChmin(c, lazy[u]); lazy[u] = INF; } } void chmin(int u, int l, int r, int ql, int qr, int v) { if (ql > r || qr < l || v >= mx[u]) return; if (ql <= l && r <= qr && v > mx2[u]) { applyChmin(u, v); return; } pushA(u); int m = (l + r) >> 1; chmin(u<<1, l, m, ql, qr, v); chmin(u<<1|1, m+1, r, ql, qr, v); pullA(u); } int qmax(int u, int l, int r, int ql, int qr) { if (ql > r || qr < l) return 0; if (ql <= l && r <= qr) return mx[u]; pushA(u); int m = (l + r) >> 1; return max(qmax(u<<1, l, m, ql, qr), qmax(u<<1|1, m+1, r, ql, qr)); } // ---- Mode B: chmax + qmin ---- inline void pullB(int u) { int lc = u<<1, rc = u<<1|1; mn[u] = min(mn[lc], mn[rc]); if (mn[lc] == mn[rc]) mn2[u] = min(mn2[lc], mn2[rc]); else if (mn[lc] < mn[rc]) mn2[u] = min(mn2[lc], mn[rc]); else mn2[u] = min(mn[lc], mn2[rc]); } void buildB(int u, int l, int r, int v) { lazy[u] = 0; // chmax 的无效标记 mn[u] = v; mn2[u] = INF; if (l == r) return; int m = (l + r) >> 1; buildB(u<<1, l, m, v); buildB(u<<1|1, m+1, r, v); } inline void applyChmax(int u, int v) { mn[u] = v; lazy[u] = max(lazy[u], v); } inline void pushB(int u) { if (lazy[u] > 0) { for (int c : {u<<1, u<<1|1}) if (mn[c] < lazy[u]) applyChmax(c, lazy[u]); lazy[u] = 0; } } void chmax(int u, int l, int r, int ql, int qr, int v) { if (ql > r || qr < l || v <= mn[u]) return; if (ql <= l && r <= qr && v < mn2[u]) { applyChmax(u, v); return; } pushB(u); int m = (l + r) >> 1; chmax(u<<1, l, m, ql, qr, v); chmax(u<<1|1, m+1, r, ql, qr, v); pullB(u); } int qmin(int u, int l, int r, int ql, int qr) { if (ql > r || qr < l) return INF; if (ql <= l && r <= qr) return mn[u]; pushB(u); int m = (l + r) >> 1; return min(qmin(u<<1, l, m, ql, qr), qmin(u<<1|1, m+1, r, ql, qr)); } } beats; // ================= 全局变量 & 数据结构实例 ================= int minRight[N], maxLeft[N], pre[N], nex[N]; int ylim1[N], ylim2[N], xlim1[N], xlim2[N], ylim[N], xlim[N]; int L[N], R[N], stk[N], sortIdx[N]; int headL[N], nxtL[N], headR[N], nxtR[N]; // 按L/R的链式前向星 int c1x[N], c1y[N], c1cnt; ll c1enc[N]; // Case1 特殊对 int insHead[N], insNxt[N], insVal[N], insTot; // 二维数点桶 SegTreeTag<int, MinOp<int>> tagTreeMin; SegTreeTag<int, MaxOp<int>> tagTreeMax; SegTreePt<int, MinOp<int>> ptTreeMin; SegTreePt<int, MaxOp<int>> ptTreeMax; // 树状数组 int bit[N]; inline void bitAdd(int i, int n) { for (; i <= n; i += i & -i) bit[i]++; } inline int bitSum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; } // 单调栈二分 template<typename Func> int stackBinSearch(int stkTop, int* stk, Func check) { if (stkTop == 0 || !check(stk[0])) return -1; int lo = 0, hi = stkTop - 1, ans = stk[0]; while (lo <= hi) { int mid = (lo + hi) >> 1; if (check(stk[mid])) { ans = stk[mid]; lo = mid + 1; } else hi = mid - 1; } return ans; } void solve() { int n = readInt(), m = readInt(); if (n < 2 || m == 0) { for (int i = 0; i < m; i++) { readInt(); readInt(); } write(0); putChar('\n'); return; } // 初始化链式前向星 for (int i = 1; i <= n + 1; ++i) headL[i] = headR[i] = -1; for (int i = 0; i < m; i++) { L[i] = readInt(); R[i] = readInt(); nxtL[i] = headL[L[i]]; headL[L[i]] = i; nxtR[i] = headR[R[i]]; headR[R[i]] = i; } // 1. 预处理 minRight / maxLeft tagTreeMin.build(1, 1, n, n + 1); for (int i = 0; i < m; ++i) tagTreeMin.update(1, 1, n, L[i], R[i], R[i]); for (int i = 1; i <= n; ++i) minRight[i] = tagTreeMin.query(1, 1, n, i); tagTreeMax.build(1, 1, n, 0); for (int i = 0; i < m; ++i) tagTreeMax.update(1, 1, n, L[i], R[i], L[i]); for (int i = 1; i <= n; ++i) maxLeft[i] = tagTreeMax.query(1, 1, n, i); // 2. 单调栈 + 二分: pre / nex int stp = 0; for (int x = 1; x <= n; x++) { int res = stackBinSearch(stp, stk, [&](int i) { return minRight[i] >= x; }); pre[x] = (res == -1) ? 0 : res; while (stp > 0 && minRight[stk[stp - 1]] <= minRight[x]) stp--; stk[stp++] = x; } stp = 0; for (int y = n; y >= 1; y--) { int res = stackBinSearch(stp, stk, [&](int i) { return maxLeft[i] <= y; }); nex[y] = (res == -1) ? n + 1 : res; while (stp > 0 && maxLeft[stk[stp - 1]] >= maxLeft[y]) stp--; stk[stp++] = y; } // 3. Case 1: 扫描线找特殊对 coverTree.build(1, 1, n); for (int i = 0; i < m; ++i) coverTree.modify(1, 1, n, L[i], R[i], 1); c1cnt = 0; for (int i = 1; i <= n; i++) { for (int j = headL[i]; j != -1; j = nxtL[j]) coverTree.modify(1, 1, n, L[j], R[j], -1); if (coverTree.mn[1] == 0 && coverTree.cnt[1] == 2) { int a = coverTree.findKthZero(1, 1, n, 1); int b = coverTree.findKthZero(1, 1, n, 2); if (a > b) swap(a, b); if (i == a || i == b) { c1x[c1cnt] = a; c1y[c1cnt] = b; c1cnt++; } } for (int j = headR[i]; j != -1; j = nxtR[j]) coverTree.modify(1, 1, n, L[j], R[j], 1); } // 去重 for (int i = 0; i < c1cnt; i++) c1enc[i] = (ll)c1x[i] * N + c1y[i]; sort(c1enc, c1enc + c1cnt); c1cnt = (int)(unique(c1enc, c1enc + c1cnt) - c1enc); for (int i = 0; i < c1cnt; i++) { c1x[i] = (int)(c1enc[i] / N); c1y[i] = (int)(c1enc[i] % N); } // 4. Case 2: 计算 ylim / xlim // ylim1: 单点 min 树, 按 R 降序扫描 iota(sortIdx, sortIdx + m, 0); sort(sortIdx, sortIdx + m, [](int a, int b) { return R[a] > R[b]; }); ptTreeMin.build(1, 1, n, n + 1); int ptr = 0; for (int x = n; x >= 1; x--) { while (ptr < m && R[sortIdx[ptr]] >= x) { int j = sortIdx[ptr++]; ptTreeMin.update(1, 1, n, L[j], R[j]); } int bound = ptTreeMin.query(1, 1, n, pre[x] + 1, x); ylim1[x] = (bound <= n) ? bound + 1 : n + 1; } // ylim2: 吉司机线段树 Mode A (chmin + qmax) beats.buildA(1, 1, n, n + 1); for (int x = n; x >= 1; x--) { if (x + 1 <= n) for (int j = headL[x + 1]; j != -1; j = nxtL[j]) beats.chmin(1, 1, n, L[j], R[j], R[j]); if (minRight[x] > n) ylim2[x] = n + 1; else if (minRight[x] == x) ylim2[x] = x + 1; else { int f = beats.qmax(1, 1, n, x + 1, minRight[x]); ylim2[x] = (f > n ? n + 1 : max(f + 1, minRight[x] + 1)); } } // xlim2: 单点 max 树, 按 L 升序扫描 sort(sortIdx, sortIdx + m, [](int a, int b) { return L[a] < L[b]; }); ptTreeMax.build(1, 1, n, 0); ptr = 0; for (int y = 1; y <= n; y++) { while (ptr < m && L[sortIdx[ptr]] <= y) { int j = sortIdx[ptr++]; ptTreeMax.update(1, 1, n, R[j], L[j]); } int bound = ptTreeMax.query(1, 1, n, y, nex[y] - 1); xlim2[y] = (bound > 0) ? bound - 1 : 0; } // xlim1: 吉司机线段树 Mode B (chmax + qmin) beats.buildB(1, 1, n, 0); for (int y = 1; y <= n; y++) { if (y >= 2) for (int j = headR[y - 1]; j != -1; j = nxtR[j]) beats.chmax(1, 1, n, L[j], R[j], L[j]); if (maxLeft[y] == 0) xlim1[y] = 0; else if (maxLeft[y] == y) xlim1[y] = y - 1; else { int h = beats.qmin(1, 1, n, maxLeft[y], y - 1); xlim1[y] = (h == 0 ? 0 : min(h - 1, maxLeft[y] - 1)); } } // 5. 二维数点 insTot = 0; for (int i = 1; i <= n + 1; i++) insHead[i] = -1; for (int x = 1; x <= n; x++) { ylim[x] = max(ylim1[x], ylim2[x]); xlim[x] = min(xlim1[x], xlim2[x]); if (ylim[x] >= 1 && ylim[x] <= n) { insNxt[insTot] = insHead[ylim[x]]; insVal[insTot] = x; insHead[ylim[x]] = insTot++; } } memset(bit, 0, sizeof(int) * (n + 1)); ll ans = 0; for (int y = 1; y <= n; y++) { for (int p = insHead[y]; p != -1; p = insNxt[p]) bitAdd(insVal[p], n); int ub = min(xlim[y], y - 1); if (ub >= 1) ans += bitSum(ub); } for (int i = 0; i < c1cnt; i++) { int x = c1x[i], y = c1y[i]; if (!(y >= ylim[x] && x <= xlim[y])) ans++; } write(ans % MOD); putChar('\n'); } int main() { int t = readInt(); while (t--) solve(); flush(); } 

吉司机线段树和分块实现两者跑出来差不多，吉司机每次操作要递归 log n 层，函数调用栈的 push/pop 本身就有成本。分块是平铺的 for 循环，零递归。这题的操作模式，初始值全相同（n+1 或 0），chmin/chmax 的值又比较集中（都是区间端点），导致吉司机的"情况 3 递归"触发频率不低，均摊优势没完全体现。而分块不管什么情况都是稳定的 O(√n)。

数据范围：

数据点0：与样例等价。
数据点1: n,m≤15，对应 2m 枚举所有可能信息的算法。
数据点2：n,m≤50，对应次数可能很高的多项式算法。
数据点3：n,m≤200，对应枚举 x,y，然后进行线性时间推理的 O(n2m) 的算法。
数据点4: n,m≤2000，对应枚举 x,y，然后使用预处理将推理时间简化到 O(1) 的算法。
数据点5：n,m≤10^5，对应上述标算。

我这份代码本质还是暴力搜索，通过随机化概率来规避复杂的逻辑推导。如果数据范围 K（离散化后的段数）较小，这个代码能跑过；但如果 N, M 达到 10^5 且区间分布很碎，这个 O(K^2) 的代码必死。

吉老师的解题报告读了好几遍，这份AC代码也是调了好几天……

顺便 问一下 @Pretty Boy Fox 你盗我代码然后把博文收费是不是多少有点活不起了？