CF2063F2 Counting Is Not Fun (Hard Version)

这是该问题的困难版本。与简单版本的区别在于，此版本对 $t$ 和 $n$ 的限制更大。仅当解决所有版本的问题时方可进行 hack。 小 John 现在很富有，终于买得起能容纳自己和最喜爱括号序列的大房子了。但不知为何，他得到了大量括号！沮丧之下，他用"佛掌"击穿了天花板。一个括号序列被称为平衡的，当且仅当其可以通过以下形式文法构造： 1. 空序列 $\varnothing$ 是平衡的。 2. 若括号序列 $A$ 是平衡的，则 $\mathtt{(}A\mathtt{)}$ 也是平衡的。 3. 若括号序列 $A$ 和 $B$ 是平衡的，则拼接序列 $AB$ 也是平衡的。 例如，序列 "(())()"、"()"、"(()(()))" 和空序列是平衡的，而 "(()" 和 "(()))(" 则不是。 给定一个平衡括号序列 $s$，当满足以下条件时，索引对 $(i,j)$（$i

每个测试包含多个测试用例。第一行包含测试用例数量 $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$ 取模。

样例中的第一个测试用例已在题目描述中解释。 第三个测试用例的解释如下：可以证明存在 $132$ 个有 $6$ 个好对的平衡括号序列。每接收一条线索后的答案如下： 1. 收到好对 $(2,3)$ 后，存在 $42$ 个符合条件的序列。 2. 收到好对 $(1,6)$ 后，存在 $5$ 个同时包含 $(2,3)$ 和 $(1,6)$ 的序列。 3. 收到好对 $(7,8)$ 后，存在 $2$ 个满足三个好对的序列，分别为 "(()())()(())" 和 "(()())()()()"。 4. 收到好对 $(9,12)$ 后，仅剩 $1$ 个满足四个好对的序列，即 "(()())()(())"。 之后的第五、第六条线索接收后答案均为 $1$，因为此时已确定唯一序列。 翻译由 DeepSeek R1 完成