CF2030G2.The Destruction of the Universe (Hard Version)

这是该问题的困难版本。在本版本中，$n \leq 10^6$。只有在两个版本都被解决后，你才能进行 hack。

猩猩是强大的存在——它们只需要 $1$ 单位时间就能摧毁宇宙中所有脆弱的星球！

宇宙中有 $n$ 个星球。每个星球都有一个脆弱区间 $[l, r]$，在这个区间内它会暴露在猩猩的毁灭之下。猩猩还可以将任意星球的脆弱区间扩展 $1$ 个单位。

具体来说，假设对第 $p$ 个星球，其脆弱区间为 $[l_p, r_p]$，进行一次扩展操作。那么，扩展后的脆弱区间可以变为 $[l_p - 1, r_p]$ 或 $[l_p, r_p + 1]$。

给定一组星球，如果所有星球的脆弱区间至少有一个公共点，则猩猩可以摧毁这组星球。该组星球的得分定义为使所有星球的脆弱区间至少有一个公共点所需的最小扩展次数。

猩猩对宇宙中所有非空星球子集的得分之和感兴趣。由于答案可能很大，请输出其对 $998\,244\,353$ 取模的结果。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）——表示宇宙中的星球数量。

接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）——表示第 $i$ 个星球的初始脆弱区间。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出一个整数——宇宙中所有非空星球子集的得分之和，对 $998\,244\,353$ 取模。

在第一个测试用例中，需要考虑七个非空星球子集：

• 对于子集 $\{[1,1]\}, \{[2,3]\}, \{[3,3]\}$，得分为 $0$。
• 对于子集 $\{[2,3], [3,3]\}$，得分为 $0$，因为点 $3$ 已经被包含在两个星球的脆弱区间内。
• 对于子集 $\{[1,1], [2,3]\}$，得分为 $1$。通过对第二个星球进行一次扩展，将其脆弱区间变为 $[1,3]$，此时两个星球的脆弱区间都包含点 $1$。
• 对于子集 $\{[1,1], [3,3]\}$，得分为 $2$。通过对第一个星球进行两次扩展，将其脆弱区间变为 $[1,3]$，此时两个星球的脆弱区间都包含点 $3$。
• 对于子集 $\{[1,1], [2,3], [3,3]\}$，得分为 $2$。通过对第一个星球扩展一次变为 $[1,2]$，对第三个星球扩展一次变为 $[2,3]$，此时三个星球的脆弱区间都包含点 $2$。

第一个测试用例中所有非空子集的得分之和为 $0 \times 4 + 1 \times 1 + 2 \times 2 = 5$。

由 ChatGPT 4.1 翻译