题解

思路

把集合大小拆成每个整数点的贡献

集合大小等于其中每个整数点的指示变量之和，因此可以固定一个整数点 $x$，只研究它最终是否属于表达式的结果。记 $b_i=[x\in S_i]$。

处理完前 $i$ 个集合后，设当前结果为假、为真的运算序列数分别为 $z_i,o_i$。加入下一位时：

• 若 $b_{i+1}=0$，则 $o_{i+1}=2o_i$；
• 若 $b_{i+1}=1$，无论先前真假，三种运算中都恰有两种得到真，所以 $o_{i+1}=2(z_i+o_i)=2\cdot3^{i-1}$。

这说明每次某条线段覆盖 $x$，它的真方案数都会被重置为只和当前编号有关的常数；之后每经过一条不覆盖 $x$ 的线段，真方案数乘二。

只看最后一次覆盖

设最后一条覆盖 $x$ 的线段编号为 $k$。

• 若 $k=1$，初始真方案数为 $1$，之后连续乘二，贡献为 $2^{n-1}$；
• 若 $k\ge2$，在第 $k$ 步被重置为 $2\cdot3^{k-2}$，之后乘了 $n-k$ 次二，贡献为

从后向前处理线段。每个整数点第一次遇到的线段，正是最后覆盖它的线段；把对应权值加入答案后，这个点以后无需再访问。

用并查集维护“当前位置及其右侧第一个尚未赋权的位置”。点 $x$ 赋权后令其父亲指向下一个未赋权点。每个坐标最多被删除一次。

做法

子任务 1：枚举全部运算序列

枚举 $3^{n-1}$ 个运算序列，对每个坐标直接模拟集合成员真假。复杂度为 $O(3^{n-1}nC)$，其中 $C$ 为坐标范围。

子任务 2：逐点两状态动态规划

对每个坐标独立扫描全部线段，维护 $(z_i,o_i)$ 并应用三种布尔运算的转移。复杂度 $O(nC)$。

子任务 3：最后覆盖权值 + 并查集

预处理二和三的幂，得到每个编号的 $w_k$。倒序扫描线段，用并查集跳过已经赋权的坐标。复杂度近似线性。

正确性证明

引理 1：固定整数点 $x$，若下一条线段不覆盖它，则真方案数变为原来的两倍；若覆盖它，则真方案数变为当前全部运算序列数的两倍。

证明：下一位为假时，并集和对称差保持真，交集变假；下一位为真时，无论原状态如何，三种运算中恰有两种结果为真。

引理 2：整数点 $x$ 的最终贡献只由最后一条覆盖它的线段编号决定，且等于题解给出的 $w_k$。

证明：最后一次覆盖时由引理 1 把真方案数重置为固定值；其后的每一步都不覆盖 $x$，由引理 1 连续乘二。$k=1$ 使用初始状态单独计算。

引理 3：倒序并查集扫描恰好为每个至少被一条线段覆盖的整数点加入一次正确权值。

证明：倒序中第一次访问一个点的线段编号最大，正是其最后覆盖编号。赋权后将其从未赋权集合中删除，因此不会重复统计；所有被覆盖点最终都会在其最大编号线段处被访问。

定理：算法输出等于所有运算序列的最终集合大小之和。

证明：由线性性，总答案是每个整数点最终为真的运算序列数之和。由引理 2、3，算法对每个点恰好加入这一数值，故结论成立。

复杂度

• 子任务 1：$O(3^{n-1}nC)$ 时间，$O(C)$ 空间。
• 子任务 2：$O(nC)$ 时间，$O(1)$ 额外空间。
• 子任务 3：$O((n+C)\alpha(C))$ 时间，$O(C+n)$ 空间，其中 $C=300001$。