← 返回题目列表

Codeforces · 2030/G2

G2. 宇宙的毁灭(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。在此版本中,$$$n \leq 10^6$$$。只有解决了两个版本的问题后,您才能进行黑客攻击。

猩猩是强大的生物,强大到它们只需要 $$$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

3
3
1 1
2 3
3 3
4
1 4
2 3
2 4
1 1
5
1 2
2 3
3 4
4 5
1 5

输出 #1

5
6
24

注意

在第一个测试用例中,我们必须考虑七个非空行星子集:

- 对于每个子集 $$$\{[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 \cdot 4 + 1 \cdot 1 + 2\cdot2 = 5$$$。