题意
有两个长度为 \(n\) 的正整数列 \(A,B\)。表示数 \(i\) 可以填到 \(A_i\) 或 \(B_i\) 两个位置中的一个。问删去空位之后可以形成的排列种数。
（\(1 \le n \le 5 \times 10^5\)，\(A_i,B_i\) 取遍 \(\left[1, 2n\right]\)）。
题解
首先可以发现填数的方案数为 \(2^n\)，发现会计算进重复情况，考虑什么时候会有重复情况，如果 \(\forall i \neq x, \left[A_i, B_i\right] \cap \left[A_x, B_x\right] = \varnothing\) 或是 \(\exists j \neq i,A_i < A_j \land B_i < B_j\) 均会产生重复情况。换句话说就是有一些数选择 \(A_i\) 和 \(B_i\) 对最终形成的排列没有影响，却被计算了多次。
设一个序列 \(C_i\)，满足 \(C_i = 0 \Rightarrow\) 数字 \(i\) 填在位置 \(A_i\)， \(C_i = 1 \Rightarrow\) 数字 \(i\) 填在位置 \(B_i\)。考虑一个数什么时候会有重复情况，如果数字 \(i\) 选择了填在 \(B_i\) 但是没有其他数字填在 \(\left(A_i, B_i\right)\)，那么这个数字就会产生重复情况，记这种状态为 \(i\) 不合法，考虑从所有状态中容斥掉不合法状态。
记 \(L_i = \max\limits_{j = 1}^{n} B_j > A_i,R_i = \min\limits_{j = 1}^{n} A_j < B_i\)，那么如果 \(i\) 不合法，可以推出 \(\forall j \in \left[L_i, i\right] C_j = 0 \land \forall j \in \left(i, R_i\right] C_j = 1\)，换句话说就是区间 \(\left[L_i,R_i\right]\) 的选择情况会被确定下来。再发现一点性质，如果存在 \(i < j\)，使得 \(R_i \ge L_j\)，那么 \(i, j\) 一定同时合法，也就是说，最终需要容斥的局面中的区间集一定两两不交。
考虑容斥，设当前的状态集合 \(S\) 为形如 \(\left\{\left(L_i, R_i\right)\right\}\) 的区间集，那么最终的答案为
\[2^n - \sum\limits_{S} (-1)^{\lvert S \rvert - 1} 2^{\operatorname{len}(S)} \]其中 \(\operatorname{len}(S) = \sum\limits_{\left(l, r\right) \in S} r - l + 1\)，即集合内所有区间的长度之和。
考虑进行容斥 DP，设 \(f_i\) 为考虑了完全包含于 \(\left[1, i\right]\) 的区间组成的状态后的方案数。边界为 \(f_0 = 2^n\)，因为没有考虑任何一个状态。考虑将所有区间按右端点存储，转移时枚举右端点为 \(i\) 的所有区间的左端点，并计算当前区间的贡献即可。转移式如下
\[f_i = \sum\limits_{R_x = i}\sum\limits_{j = 0}^{L_x - 1} -2^{-(R_x - L_x + 1)}f_j \]使用前缀和优化即可以 \(\mathcal{O}(n)\) 的复杂度通过本题。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
constexpr valueType MOD = 998244353;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % MOD;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
class Inverse {
public:
typedef ValueVector container;
private:
valueType size;
container data;
public:
explicit Inverse(valueType n) : size(n), data(size + 1, 0) {
data[1] = 1;
for (valueType i = 2; i <= size; ++i)
data[i] = mul((MOD - MOD / i), data[MOD % i]);
}
valueType operator()(valueType n) const {
return data[n];
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N;
std::cin >> N;
ValueVector A(N + 1), B(N + 1), L(N + 1), R(N + 1);
for (valueType i = 1; i <= N; ++i)
std::cin >> A[i] >> B[i];
valueType pointer = 0;
for (valueType i = 1; i <= N; ++i) {
while (pointer < N && B[pointer + 1] < A[i])
++pointer;
L[i] = pointer + 1;
}
pointer = N + 1;
for (valueType i = N; i >= 1; --i) {
while (pointer > 1 && A[pointer - 1] > B[i])
--pointer;
R[i] = pointer - 1;
}
ValueMatrix left(N + 1);
for (valueType i = 1; i <= N; ++i)
left[R[i]].emplace_back(L[i]);
ValueVector F(N + 1, 0);
F[0] = pow(2, N);
Inverse Inv(2);
for (valueType i = 1; i <= N; ++i) {
Inc(F[i], F[i - 1]);
for (auto const &iter: left[i])
Dec(F[i], mul(pow(Inv(2), i - iter + 1), F[iter - 1]));
}
std::cout << F[N] << std::endl;
return 0;
}