PTA 团体程序设计天梯赛 L3-036 血染钟楼
题目描述
九条可怜最近非常沉迷血染钟楼 —— 一款类狼人杀的身份推理类的游戏。在一局血染钟楼的游戏中，玩家们之间隐藏着一名'恶魔'，而所有善良玩家的目标就是将抽到恶魔身份的玩家绳之以法。
今天，九条可怜和她的小伙伴们开了一局 n+1 名玩家参与的游戏，可怜的编号是 0，其他玩家编号从 1 到 n。 可怜抽到的身份是占卜师，其技能如下（注意这儿和标准钟楼规则有出入）：
- 每个夜晚，你可以选择任意名玩家，并得知被选择的玩家中是否有恶魔。
- 有一名除你以外善良玩家始终被你的能力视为恶魔。
换句话说，在剩下的 n 名玩家中，存在着两名未知的玩家，如果这两名玩家均未被可怜选中，可怜就会得到信息 0，否则就会得到信息 1。 在抽到身份的时候，可怜就对游戏开始的前 m 个夜晚进行了规划：她打算在第 i 个夜晚选中编号在区间 [l_i, r_i] 内的所有玩家。 因为血染钟楼的第一个夜晚通常比较漫长，所以可怜在百无聊赖之际开始了头脑风暴。如果一切顺利，在 m 晚之后，她将能得到 m 个 0 或 1 的信息，共有 2^m 种不同的可能性。可怜想要知道在这些可能性中，有多少种结果是可能发生的且可以让她唯一确定被她技能识别的两名玩家。
输入格式
第一行输入一个整数 t(1≤t≤10^3)，表示数据组数。 第二行输入两个整数 n,m(1≤n,m≤10^5)，表示可怜以外的玩家数量以及可怜规划的夜晚数量。 接下来 m 行每行两个整数 l_i,r_i(1≤l_i≤r_i≤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
解题思路
将问题分为两类讨论：
Case 1：特殊对（退化情况） 存在某个位置 i，使得去掉所有左端点恰好为 i 的区间后，恰好有 2 个位置未被覆盖（记为 a < b），且 i ∈ {a, b}。 这类点对的特征是：所有覆盖 x 或 y 的区间都'经过'同一个关键点，去掉这些区间后恰好只暴露出 x 和 y。 实现：用一棵支持区间加、全局最小值计数、第 k 个零位置查询的线段树进行扫描线处理。
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 的区间中最大左端点）。使用标记永久化线段树完成。
- pre 和 nex：pre[x] 是 x 左边最远的与 x 纠缠的位置；nex[y] 对称。通过线段树二分实现。
- ylim 和 xlim 的计算：
- ylim1[x]：利用单点修改线段树维护。
- ylim2[x]：利用 Segment Tree Beats（区间 chmin + 查 max）维护桥梁连通性约束。
- xlim 计算完全对称。
- 二维数点：统计满足 y >= ylim[x] 且 x <= xlim[y] 且 x < y 的对数。
代码实现
C++ 版本（吉司机线段树）
// 血染钟楼 L3-036 — 吉司机线段树版
#pragma GCC optimize()
std;
ll;
MOD = , N = , INF = + ;
IO {
SZ = << ;
ib[SZ], *ip = ib, *ie = ib, ob[SZ];
op = ;
{ ip == ie && (ie = (ip = ib) + (ib, , SZ, stdin), ip == ie) ? EOF : *ip++; }
{ x = ; c = (); (c < || c > ) c = (); (c >= && c <= ) { x = x * + c - ; c = (); } x; }
{ (op == SZ) { (ob, , SZ, stdout); op = ; } ob[op++] = c; }
{ (x > ) (x / ); (x % + ); }
{ (ob, , op, stdout); op = ; }
}
IO::readInt; IO::write; IO::putChar; IO::flush;
{ id = INF; { (a, b); } };
{ id = ; { (a, b); } };
< T, Op> {
T t[N << ]; Op op;
{ t[u] = init_val; (l == r) ; m = (l + r) >> ; (u<<, l, m, init_val); (u<<|, m, r, init_val); }
{ (ql > r || qr < l) ; (ql <= l && r <= qr) { t[u] = (t[u], v); ; } m = (l + r) >> ; (u<<, l, m, ql, qr, v); (u<<|, m, r, ql, qr, v); }
{ (l == r) t[u]; m = (l + r) >> ; (t[u], p <= m ? (u<<, l, m, p) : (u<<|, m, r, p)); }
};
< T, Op> {
T t[N << ]; Op op; T init_v;
{ t[u] = init_v = iv; (l == r) ; m = (l + r) >> ; (u<<, l, m, iv); (u<<|, m, r, iv); }
{ (l == r) { t[u] = (t[u], v); ; } m = (l + r) >> ; (p <= m) (u<<, l, m, p, v); (u<<|, m, r, p, v); t[u] = (t[u<<], t[u<<|]); }
{ (ql > r || qr < l) init_v; (ql <= l && r <= qr) t[u]; m = (l + r) >> ; ((u<<, l, m, ql, qr), (u<<|, m, r, ql, qr)); }
};
{
mn[N << ], cnt[N << ], lazy[N << ];
{
lc = u<<, rc = u<<|;
(mn[lc] < mn[rc]) { mn[u] = mn[lc]; cnt[u] = cnt[lc]; }
(mn[lc] > mn[rc]) { mn[u] = mn[rc]; cnt[u] = cnt[rc]; }
{ mn[u] = mn[lc]; cnt[u] = cnt[lc] + cnt[rc]; }
}
{ mn[u] = lazy[u] = ; cnt[u] = r - l + ; (l == r) ; m = (l + r) >> ; (u<<, l, m); (u<<|, m, r); }
{ mn[u] += v; lazy[u] += v; }
{ (lazy[u]) { (u<<, lazy[u]); (u<<|, lazy[u]); lazy[u] = ; } }
{
(ql > r || qr < l) ; (ql <= l && r <= qr) { (u, v); ; }
(u); m = (l + r) >> ; (u<<, l, m, ql, qr, v); (u<<|, m, r, ql, qr, v); (u);
}
{
(l == r) l; (u); m = (l + r) >> ;
leftZeros = (mn[u<<] == ? cnt[u<<] : );
(k <= leftZeros) (u<<, l, m, k);
(u<<|, m, r, k - leftZeros);
}
} coverTree;
{
mx[N << ], mx2[N << ], mn[N << ], mn2[N << ], lazy[N << ];
{
lc = u<<, rc = u<<|; mx[u] = (mx[lc], mx[rc]);
(mx[lc] == mx[rc]) mx2[u] = (mx2[lc], mx2[rc]);
(mx[lc] > mx[rc]) mx2[u] = (mx2[lc], mx[rc]);
mx2[u] = (mx[lc], mx2[rc]);
}
{ lazy[u] = INF; mx[u] = v; mx2[u] = ; (l == r) ; m = (l + r) >> ; (u<<, l, m, v); (u<<|, m, r, v); }
{ mx[u] = v; lazy[u] = (lazy[u], v); }
{ (lazy[u] < INF) { ( c : {u<<, u<<|}) (mx[c] > lazy[u]) (c, lazy[u]); lazy[u] = INF; } }
{
(ql > r || qr < l || v >= mx[u]) ;
(ql <= l && r <= qr && v > mx2[u]) { (u, v); ; }
(u); m = (l + r) >> ; (u<<, l, m, ql, qr, v); (u<<|, m, r, ql, qr, v); (u);
}
{
(ql > r || qr < l) ; (ql <= l && r <= qr) mx[u]; (u); m = (l + r) >> ;
((u<<, l, m, ql, qr), (u<<|, m, r, ql, qr));
}
{
lc = u<<, rc = u<<|; mn[u] = (mn[lc], mn[rc]);
(mn[lc] == mn[rc]) mn2[u] = (mn2[lc], mn2[rc]);
(mn[lc] < mn[rc]) mn2[u] = (mn2[lc], mn[rc]);
mn2[u] = (mn[lc], mn2[rc]);
}
{ lazy[u] = ; mn[u] = v; mn2[u] = INF; (l == r) ; m = (l + r) >> ; (u<<, l, m, v); (u<<|, m, r, v); }
{ mn[u] = v; lazy[u] = (lazy[u], v); }
{ (lazy[u] > ) { ( c : {u<<, u<<|}) (mn[c] < lazy[u]) (c, lazy[u]); lazy[u] = ; } }
{
(ql > r || qr < l || v <= mn[u]) ;
(ql <= l && r <= qr && v < mn2[u]) { (u, v); ; }
(u); m = (l + r) >> ; (u<<, l, m, ql, qr, v); (u<<|, m, r, ql, qr, v); (u);
}
{
(ql > r || qr < l) INF; (ql <= l && r <= qr) mn[u]; (u); m = (l + r) >> ;
((u<<, l, m, ql, qr), (u<<|, m, r, ql, qr));
}
} beats;
minRight[N], maxLeft[N], pre[N], nex[N];
ylim1[N], ylim2[N], xlim1[N], xlim2[N], ylim[N], xlim[N];
L[N], R[N], stk[N], sortIdx[N];
headL[N], nxtL[N], headR[N], nxtR[N];
c1x[N], c1y[N], c1cnt; ll c1enc[N];
insHead[N], insNxt[N], insVal[N], insTot;
bit[N];
{ (; i <= n; i += i & -i) bit[i]++; }
{ s = ; (; i > ; i -= i & -i) s += bit[i]; s; }
{
(stkTop == || !(stk[])) ;
lo = , hi = stkTop - , ans = stk[];
(lo <= hi) { mid = (lo + hi) >> ; ((stk[mid])) { ans = stk[mid]; lo = mid + ; } hi = mid - ; }
ans;
}
{
n = (), m = ();
(n < || m == ) { ( i = ; i < m; i++) { (); (); } (); (); ; }
( i = ; i <= n + ; ++i) headL[i] = headR[i] = ;
( i = ; i < m; i++) { L[i] = (); R[i] = (); nxtL[i] = headL[L[i]]; headL[L[i]] = i; nxtR[i] = headR[R[i]]; headR[R[i]] = i; }
SegTreeTag<, MinOp<>> tagTreeMin; SegTreeTag<, MaxOp<>> tagTreeMax;
SegTreePt<, MinOp<>> ptTreeMin; SegTreePt<, MaxOp<>> ptTreeMax;
tagTreeMin.(, , n, n + ); ( i = ; i < m; ++i) tagTreeMin.(, , n, L[i], R[i], R[i]);
( i = ; i <= n; ++i) minRight[i] = tagTreeMin.(, , n, i);
tagTreeMax.(, , n, ); ( i = ; i < m; ++i) tagTreeMax.(, , n, L[i], R[i], L[i]);
( i = ; i <= n; ++i) maxLeft[i] = tagTreeMax.(, , n, i);
stp = ;
( x = ; x <= n; x++) {
res = (stp, stk, [&]( i) { minRight[i] >= x; });
pre[x] = (res == ) ? : res;
(stp > && minRight[stk[stp - ]] <= minRight[x]) stp--; stk[stp++] = x;
}
stp = ;
( y = n; y >= ; y--) {
res = (stp, stk, [&]( i) { maxLeft[i] <= y; });
nex[y] = (res == ) ? n + : res;
(stp > && maxLeft[stk[stp - ]] >= maxLeft[y]) stp--; stk[stp++] = y;
}
coverTree.(, , n); ( i = ; i < m; ++i) coverTree.(, , n, L[i], R[i], );
c1cnt = ;
( i = ; i <= n; i++) {
( j = headL[i]; j != ; j = nxtL[j]) coverTree.(, , n, L[j], R[j], );
(coverTree.mn[] == && coverTree.cnt[] == ) {
a = coverTree.(, , n, ); b = coverTree.(, , n, );
(a > b) (a, b); (i == a || i == b) { c1x[c1cnt] = a; c1y[c1cnt] = b; c1cnt++; }
}
( j = headR[i]; j != ; j = nxtR[j]) coverTree.(, , n, L[j], R[j], );
}
( i = ; i < c1cnt; i++) c1enc[i] = (ll)c1x[i] * N + c1y[i];
(c1enc, c1enc + c1cnt); c1cnt = ()((c1enc, c1enc + c1cnt) - c1enc);
( i = ; i < c1cnt; i++) { c1x[i] = ()(c1enc[i] / N); c1y[i] = ()(c1enc[i] % N); }
(sortIdx, sortIdx + m, ); (sortIdx, sortIdx + m, []( a, b) { R[a] > R[b]; });
ptTreeMin.(, , n, n + ); ptr = ;
( x = n; x >= ; x--) {
(ptr < m && R[sortIdx[ptr]] >= x) { j = sortIdx[ptr++]; ptTreeMin.(, , n, L[j], R[j]); }
bound = ptTreeMin.(, , n, pre[x] + , x); ylim1[x] = (bound <= n) ? bound + : n + ;
}
beats.(, , n, n + );
( x = n; x >= ; x--) {
(x + <= n) ( j = headL[x + ]; j != ; j = nxtL[j]) beats.(, , n, L[j], R[j], R[j]);
(minRight[x] > n) ylim2[x] = n + ; (minRight[x] == x) ylim2[x] = x + ;
{ f = beats.(, , n, x + , minRight[x]); ylim2[x] = (f > n ? n + : (f + , minRight[x] + )); }
}
(sortIdx, sortIdx + m, []( a, b) { L[a] < L[b]; });
ptTreeMax.(, , n, ); ptr = ;
( y = ; y <= n; y++) {
(ptr < m && L[sortIdx[ptr]] <= y) { j = sortIdx[ptr++]; ptTreeMax.(, , n, R[j], L[j]); }
bound = ptTreeMax.(, , n, y, nex[y] - ); xlim2[y] = (bound > ) ? bound - : ;
}
beats.(, , n, );
( y = ; y <= n; y++) {
(y >= ) ( j = headR[y - ]; j != ; j = nxtR[j]) beats.(, , n, L[j], R[j], L[j]);
(maxLeft[y] == ) xlim1[y] = ; (maxLeft[y] == y) xlim1[y] = y - ;
{ h = beats.(, , n, maxLeft[y], y - ); xlim1[y] = (h == ? : (h - , maxLeft[y] - )); }
}
insTot = ; ( i = ; i <= n + ; i++) insHead[i] = ;
( x = ; x <= n; x++) {
ylim[x] = (ylim1[x], ylim2[x]); xlim[x] = (xlim1[x], xlim2[x]);
(ylim[x] >= && ylim[x] <= n) { insNxt[insTot] = insHead[ylim[x]]; insVal[insTot] = x; insHead[ylim[x]] = insTot++; }
}
(bit, , () * (n + )); ll ans = ;
( y = ; y <= n; y++) {
( p = insHead[y]; p != ; p = insNxt[p]) (insVal[p], n);
ub = (xlim[y], y - ); (ub >= ) ans += (ub);
}
( i = ; i < c1cnt; i++) { x = c1x[i], y = c1y[i]; (!(y >= ylim[x] && x <= xlim[y])) ans++; }
(ans % MOD); ();
}
{ t = (); (t--) (); (); ; }
