这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$t$$$ 和 $$$n$$$ 的限制更大。只有解决了该问题的所有版本,您才能破解。
现在小约翰很富有,所以他终于买了一座足够大的房子来容纳他自己和他最喜欢的括号序列。但不知何故,他最终得到了很多括号!沮丧之下,他用“佛掌”刺穿了天花板。
如果括号序列可以通过以下形式语法构造,则称为平衡括号序列。
1. 空序列 $$$\varnothing$$$ 是平衡的。
2. 如果括号序列 $$$A$$$ 是平衡的,则 $$$\mathtt{(}A\mathtt{)}$$$ 也是平衡的。
3. 如果括号序列 $$$A$$$ 和 $$$B$$$ 是平衡的,则串联序列 $$$A B$$$ 也是平衡的。
例如,序列“(())()”、“()”、“(()(()))”和空序列是平衡的,而“(()”和“(()))(”不是平衡的。
给定一个平衡的括号序列$$$s$$$,如果$$$s_i$$$是'(',$$$s_j$$$是')',一对索引$$$(i,j)$$$ ($$$i<j$$$)被称为好对,并且在构造序列$$$s$$$时根据规则2同时添加两个括号。例如,序列“(())()”具有三个不同的好对,分别是$$$(1,4)$$$、$$$(2,3)$$$和$$$(5,6)$$$。可以证明任何 $$$2n$$$ 括号的平衡括号序列恰好包含 $$$n$$$ 个不同的好对,并且使用任何规则顺序构造相同的括号序列将产生相同的一组好对。
艾米丽将与约翰玩括号猜谜游戏。游戏玩法如下。
最初,John 有一个平衡括号序列 $$$s$$$,其中包含 $$$n$$$ 不同的好对,而 Emily 并不知道。约翰告诉艾米丽 $$$n$$$ 的值,并要求艾米丽猜测序列。
在 $$$n$$$ 个回合中,约翰在每个回合中都会向艾米丽提供以下线索。
- $$$l\;r$$$:序列$$$s$$$包含一个好的对$$$(l,r)$$$。
约翰给艾米丽的线索是两两不同且不矛盾的。
在某一时刻,艾米丽可以确定满足目前给出的线索的平衡括号序列是唯一的。例如,假设 Emily 知道 $$$s$$$ 有 $$$3$$$ 好对,并且它包含好对 $$$(2,5)$$$。在具有 $$$3$$$ 好对的 $$$5$$$ 平衡括号序列中,仅存在一个具有好对 $$$(2,5)$$$ 的序列“((()))”。因此,可以看出,Emily并不总是需要$$$n$$$轮流来猜测$$$s$$$。
为了尽早找出$$$s$$$的内容,Emily想知道每回合后与线索匹配的不同平衡括号序列的数量。当然,这对艾米丽来说并不是一件容易的事,尤其是当她得到了这么多好鞋的时候。现在轮到你帮助艾米丽了。有了线索,你必须在每个回合之前和之后找到答案。由于答案可能很大,您需要对 $$$998\,244\,353$$$ 求模。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 好对的数量。
然后,接下来的 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ 代表第 $$$i$$$ 条线索 ($$$1 \le l_i < r_i \le 2n$$$)。
一个测试用例中的线索是两两不同且彼此不矛盾的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上输出 $$$n+1$$$ 整数:
- 第一个整数是所有线索之前的答案,模 $$$998\,244\,353$$$。
- 对于所有 $$$i \ge 1$$$,第 $$$i+1$$$ 个整数是第 $$$i$$$ 个线索之后的答案,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
3 3 2 5 1 6 3 4 4 1 6 7 8 2 3 4 5 6 2 3 1 6 7 8 9 12 10 11 4 5
输出 #1
5 1 1 1 14 2 2 1 1 132 42 5 2 1 1 1
注意
示例的第一个测试用例在问题描述中进行了解释。
示例的第三个测试用例解释如下。可以证明,存在 $$$132$$$ 平衡括号序列和 $$$6$$$ 好对。每条线索后的答案如下:
1. 你得到了好对$$$(2,3)$$$。有 $$$42$$$ 平衡括号序列具有良好的配对 $$$(2,3)$$$。
2. 你得到了好对 $$$(1,6)$$$。有 $$$5$$$ 平衡括号序列具有良好的配对 $$$(2,3)$$$、$$$(1,6)$$$。
3. 你得到了好对 $$$(7,8)$$$。有 $$$2$$$ 平衡括号序列具有三个好对。字符串分别为“(()())()(())”和“(()())()()()”。
4. 你得到了好对 $$$(9,12)$$$。只有一个平衡括号序列具有四对好对。因此,$$$s$$$ 的内容是唯一的字符串,即“(()())()(())”。
那么,第五条和第六条线索之后的括号序列数都是$$$1$$$,因为你已经知道了$$$s$$$的内容。