给定 $ n $ 个区间 $ [x_i, y_i] $，保证所有区间均不同。令 $ f(l, r) $ 表示从 $ n $ 个区间中选择偶数个区间使得其并集恰为 $ [l, r] $ 的方案数，$ g(l, r) $ 表示从 $ n $ 个区间中选择奇数个区间使得其并集恰为 $ [l, r] $ 的方案数。给定 $ q $ 组询问 $ [l_i, r_i] $，求 $ f(l_i, r_i) - g(l_i, r_i) $。答案对 $ 998244353 $ 取模。
\(n,q \leq 2 \times 10^5\)，\(x_i,y_i,l_i,r_i \leq 10^9\)
好题。第一反应是，并集为 \([l,r]\) 的方案数是否是能求的。如果它能求，结合题目问的东西，那我们甚至能够解出 \(f(l_i,r_i)\) 和 \(g(l_i,r_i)\)——这看起来就不太可能。这意味着，\(f(l_i,r_i)-g(l_i,r_i)\) 这个式子其实很可能隐含着某些性质，使得我们真正需要计算的东西能够被简化。
容易有这样的想法：如果存在某条线段 \(I\)，选不选择它并不会改变并集，那么这两种方案会各在 \(f(l_i,r_i)\) 和 \(g(l_i,r_i)\) 中贡献一次，因此对答案的贡献是 \(0\)！于是对于两条线段 \(I \in J\)，如果选择了 \(J\)，那么对答案的贡献是 \(0\)，因此我们可以直接把 \(J\) 删掉。
事实上，我们还能够由此推出更多的东西。对于一组询问 \([l_i,r_i]\)，考虑所有完全被包含的线段，将它们按照左端点排序。由于现在线段没有包含关系，因此右端点也是排好序的。考虑连续的 \(3\) 条线段，如果满足 \(l_1 < l_2 < l_3 < r_1\)，那么如果同时选择了 \(1\) 和 \(3\)，那么 \(2\) 是否选择不会改变并集，于是这种方案对答案的贡献也是 \(0\)。由于 \(1\) 必须选择，此时我们可以把 \(3\) 删去。
同理，我们可以推出此时 \(2\) 又是必须选择的，且可以删掉后面的一些线段。按此不断推下去，剩下的所有线段都必须被选择，所以如果剩下 \(k\) 条线段满足并集为 \([l_i,r_i]\)，那么答案为 \((-1)^k\)，否则答案是 \(0\)。
考虑如何解决多组询问。想想对于一组询问 \([L,R]\) 我们实际上做了什么：我们找到了一条左端点为 \(L\) 的线段和一条左端点大于 \(L\) 且最小的两条线段作为起始线段 \(1,2\)，然后从 \(1\) 开始，找到左端点大于 \(r_1\) 且最小的线段 \(3\)，然后再对 \(2\) 做，依次做下去直到右端点到达了 \(R\)。容易想到预处理：对于线段 \(i\)，找到最小的 \(j\) 满足 \(r_i < l_j\)，连边 \(i \to j\)。这样所有边会形成一个森林，每次询问倍增跳即可。
注意，如果最终跳到的线段相同，中间一定存在一段空隙没有被任何线段覆盖，答案是 \(0\)。否则容易通过倍增的步数判断 \(k\) 的奇偶性，总时间复杂度 \(\mathcal{O}((n+q)\log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 5, mod = 998244353, inf = 1e9 + 5;
int n, m, cnt, f[N][20];
struct seg {
int l, r;
bool operator < (const seg &p) const {
if (l == p.l) return r > p.r;
return l < p.l;
}
} a[N], b[N];
int get(int x) {
return lower_bound(b + 1, b + cnt + 1, (seg){x, inf}) - b;
}
int qry(int l, int r) {
int u = get(l);
if (u > cnt || b[u].l != l) return 0;
if (b[u].r == r) return mod - 1;
int v = get(l + 1);
if (v > cnt || b[v].l > b[u].r) return 0;
if (b[v].r > r) return 0;
int c = 0;
for (int i = 19; i >= 0; i--) {
if (f[u][i] <= cnt && b[f[u][i]].r <= r) {
u = f[u][i];
if (i == 0) c ^= 1;
}
}
for (int i = 19; i >= 0; i--) {
if (f[v][i] <= cnt && b[f[v][i]].r <= r) {
v = f[v][i];
if (i == 0) c ^= 1;
}
}
if (u == v) return 0;
if (b[u].r == r || b[v].r == r) {
if (c) return mod - 1;
return 1;
}
return 0;
}
signed main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
sort(a + 1, a + n + 1);
int cur = inf;
for (int i = n; i >= 1; i--) {
if (a[i].r >= cur) continue;
cur = min(cur, a[i].r), b[++cnt] = a[i];
}
sort(b + 1, b + cnt + 1);
int k = 1;
for (int i = 1; i <= cnt; i++) {
while (k <= cnt && b[k].l <= b[i].r) k++;
f[i][0] = k;
}
for (int i = 0; i <= 19; i++) f[cnt + 1][i] = cnt + 1;
for (int i = 1; i <= 19; i++) {
for (int j = 1; j <= cnt; j++) {
f[j][i] = f[f[j][i - 1]][i - 1];
}
}
while (m--) {
int l, r; cin >> l >> r;
cout << qry(l, r) << "\n";
}
return 0;
}