随笔题解 Pb. 5
2022 年 10 月 17 日 22：35 ~ 次日 00：35，AHU 2021 届不知名 ACM 选手関原みや（化名）报名参加 Educational Codeforces Round 137 (Rated for Div. 2)。期间因急了，C 题 WA 1 发，（某数据随机复杂度虚伪的）D 题 WA 4 发；但最后关头潜力爆发，做出 F 题并成功上分，跻身 Candidate Master 之列。距今已过……不知道多久，佳话永流传。
来源：CF1743 F Intersection and Union
给定 $n$ 个集合 $S_1,S_2,\dots,S_n$，其中 $S_i=[l_i,r_i]\cap\mathbb{Z}$。
现构造操作序列 $p_1,p_2,\dots,p_{n-1}$，其中 $p_i\in\{\cup,\cap,\oplus\}$，$\cup$ 表示集合的并，$\cap$ 表示集合的交，$\oplus$ 表示集合的对称差。
显然整个操作序列 $p$ 一共有 $3^{n-1}$ 中方案。试对于每种 $p$，计算
的和。对 $998244353$ 取模。
$2\leqslant n\leqslant 3\times 10^5$，$0\leqslant l_i\leqslant r_i\leqslant 3\times 10^5$。
$\mathtt{5s/512MB}$。
令 $T_k$ 表示下式的计算结果
可以大致看成是 $S_k$ 的前缀和。
考虑对于每个 $x$，计算有多少种方案使得 $x\in T_n$。
设当前考察到 $T_{k-1}$。并且有 $x\not\in S_k$，那么：
- 如果 $x\not\in T_{k-1}$，无论 $p_k$ 如何取值，总有 $x\not\in T_k$。
- 如果 $x\in T_{k-1}$，$p_k=\cap$，那么 $x\not\in T_k$。
- 如果 $x\in T_{k-1}$，$p_k=\cup$ 或 $p_k=\oplus$，那么 $x\in T_k$。
同理，如果 $x\in S_k$，那么：
- 如果 $x\not\in T_{k-1}$，$p_k=\cap$，那么 $x\not\in T_k$。
- 如果 $x\not\in T_{k-1}$，$p_k=\cup$ 或 $p_k=\oplus$，那么 $x\in T_k$。
- 如果 $x\in T_{k-1}$，$p_k=\oplus$，那么 $x\not\in T_k$。
- 如果 $x\in T_{k-1}$，$p_k=\cup$ 或 $p_k=\cap$，那么 $x\in T_k$。
设 $f(k,0/1,0/1)$：其中 $f(k,0,0)$ 表示在 $x\not\in T_{k-1}$ 的情况下，$x\not\in T_k$ 的方案数；剩余状态的含义可以以此类推。我们可以整理出：
这样我们只需从小到大扫一遍 $x$，用扫描线处理出每个 $S_k$ 是否包含当前 $x$，然后再用线段树维护单点修改和区间矩阵乘积即可。
当然还有一些细节，比如说 $S_1$ 这个位置有些特殊，所以实际上求解矩阵乘积的时候求解的是 $[2,n]$ 上的乘积，然后再根据是否有 $x\in S_1$ 单独计算 $S_1$ 产生的贡献。
还有就是，如果 $x\not\in\bigcup S_i$，那么这个 $x$ 不应该参与计算。