Counting Is Not Fun (Hard Version)
Contest: Codeforces Round 1000 (Div. 2)
Difficulty rating: 2700
Tags: combinatorics, data structures, dfs and similar, dsu, graphs, implementation, trees

This is the hard version of the problem. The difference between the versions is that in this version, the limits on $$$t$$$ and $$$n$$$ are bigger. You can hack only if you solved all versions of this problem.

Now Little John is rich, and so he finally buys a house big enough to fit himself and his favorite bracket sequence. But somehow, he ended up with a lot of brackets! Frustrated, he penetrates through the ceiling with the "buddha palm".

A bracket sequence is called balanced if it can be constructed by the following formal grammar.

1. The empty sequence $$$\varnothing$$$ is balanced.
2. If the bracket sequence $$$A$$$ is balanced, then $$$\mathtt{(}A\mathtt{)}$$$ is also balanced.
3. If the bracket sequences $$$A$$$ and $$$B$$$ are balanced, then the concatenated sequence $$$A B$$$ is also balanced.

For example, the sequences "(())()", "()", "(()(()))", and the empty sequence are balanced, while "(()" and "(()))(" are not.

Given a balanced bracket sequence $$$s$$$, a pair of indices $$$(i,j)$$$ ($$$i<j$$$) is called a good pair if $$$s_i$$$ is '(', $$$s_j$$$ is ')', and the two brackets are added simultaneously with respect to Rule 2 while constructing the sequence $$$s$$$. For example, the sequence "(())()" has three different good pairs, which are $$$(1,4)$$$, $$$(2,3)$$$, and $$$(5,6)$$$. One can show that any balanced bracket sequence of $$$2n$$$ brackets contains exactly $$$n$$$ different good pairs, and using any order of rules to construct the same bracket sequence will yield the same set of good pairs.

Emily will play a bracket guessing game with John. The game is played as follows.

Initially, John has a balanced bracket sequence $$$s$$$ containing $$$n$$$ different good pairs, which is not known to Emily. John tells Emily the value of $$$n$$$ and asks Emily to guess the sequence.

Throughout $$$n$$$ turns, John gives Emily the following kind of clue on each turn.

- $$$l\;r$$$: The sequence $$$s$$$ contains a good pair $$$(l,r)$$$.

The clues that John gives Emily are pairwise distinct and do not contradict each other.

At a certain point, Emily can be certain that the balanced bracket sequence satisfying the clues given so far is unique. For example, assume Emily knows that $$$s$$$ has $$$3$$$ good pairs, and it contains the good pair $$$(2,5)$$$. Out of $$$5$$$ balanced bracket sequences with $$$3$$$ good pairs, there exists only one such sequence "((()))" with the good pair $$$(2,5)$$$. Therefore, one can see that Emily does not always need $$$n$$$ turns to guess $$$s$$$.

To find out the content of $$$s$$$ as early as possible, Emily wants to know the number of different balanced bracket sequences that match the clues after each turn. Surely, this is not an easy job for Emily, especially when she is given so many good pairs. Now it is your turn to help Emily. Given the clues, you must find the answer before and after each turn. As the answers may be huge, you need to find them modulo $$$998\,244\,353$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of good pairs.

Then, each of the $$$n$$$ following lines contains two integers $$$l_i$$$ and $$$r_i$$$ representing the $$$i$$$-th clue ($$$1 \le l_i < r_i \le 2n$$$).

The clues in one test case are pairwise distinct and do not contradict each other.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output $$$n+1$$$ integers on a separate line:

- The first integer is the answer before all clues, modulo $$$998\,244\,353$$$.
- For all $$$i \ge 1$$$, the $$$i+1$$$-th integer is the answer after the $$$i$$$-th clue, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
The first test case of the example is explained in the problem description.

The third test case of the example is explained as follows. It can be shown that there are $$$132$$$ balanced bracket sequences with $$$6$$$ good pairs. The answers after each clue are given as follows:

1. You are given the good pair $$$(2,3)$$$. There are $$$42$$$ balanced bracket sequences having the good pair $$$(2,3)$$$.
2. You are given the good pair $$$(1,6)$$$. There are $$$5$$$ balanced bracket sequences having good pairs $$$(2,3)$$$, $$$(1,6)$$$.
3. You are given the good pair $$$(7,8)$$$. There are $$$2$$$ balanced bracket sequences having the three good pairs. The strings are "(()())()(())" and "(()())()()()", respectively.
4. You are given the good pair $$$(9,12)$$$. There is only one balanced bracket sequence having the four good pairs. The content of $$$s$$$ is therefore the only string, which is "(()())()(())".

Then, the number of bracket sequences after the fifth and the sixth clue are both $$$1$$$ as you already know the content of $$$s$$$.

Example input:
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

Example output:
5 1 1 1
14 2 2 1 1
132 42 5 2 1 1 1

Editorial:
If you have not read the editorial for the easy subtask, I strongly suggest you to read it first. It contains some important observations that carry on to the solution of the hard subtask.
The easy subtask's solution relied on enumerating the "minimal balanced subsequences". (We will use this same term repeatedly in the hard subtask's editorial, so we abbreviate it to "MBS(es)" for convenience. Note that, as opposed to the easy version, the definition of MBSes in the hard version's editorial includes the good pairs themselves.) Now, the hard subtask makes it impossible to use the $$$\mathcal{O}(n^2)$$$ solution, so we cannot enumerate the MBSes. The hard subtask asks for a more clever approach.
An important observation for the hard subtask is as follows:
• Observation: When a new good pair is added, in fact, most MBSes do not change.
If a good pair is added on an MBS $$$a$$$ which is enclosed by another MBS $$$b$$$, the MBS $$$b$$$ does not change because the good pair does not give any additional information about $$$b$$$. (It just gave the information that some supersequence of $$$b$$$ is balanced, but that doesn't make any additional information about $$$b$$$.)
If a good pair is added on an MBS $$$c$$$ which encloses another MBS $$$d$$$, the MBS $$$d$$$ does not change because the good pair does not give any additional information about $$$d$$$. (It just gave the information that some supersequence of $$$d$$$ is balanced, but that doesn't make any additional information about $$$d$$$.)
If a good pair is added on an MBS $$$e$$$ and there is another MBS $$$f$$$ not enclosing/enclosed by it, the MBS $$$f$$$ does not change either; the two MBSes are simply independent.
Therefore, when the good pair is added on an MBS $$$S$$$, the only MBS that changes is $$$S$$$, and all other MBSes do not change.
Let's observe what happens when a good pair is added on an MBS $$$S$$$. Precisely the following things happen according to the information that this good pair adds:
• As the subsequence inside the good pair must be balanced, the subsequence containing indices inside the good pair becomes a new MBS (assuming that it exists).
• As the subsequence outside the good pair must be balanced, the subsequence containing indices outside the good pair becomes a new MBS (assuming that it exists).
• The good pair itself becomes a new MBS, assuming the MBS $$$S$$$ was not a single good pair.
Thus, the MBS splits into at most three new MBSes upon the addition of a good pair.
For example, if the MBS $$$S$$$ was $$$[1,2,5,6,7,8,11,12,13,14]$$$, and the good pair is $$$(5,12)$$$, the MBS splits to three following MBSes:
• $$$[6,7,8,11]$$$ inside the good pair;
• $$$[1,2,13,14]$$$ outside the good pair;
• $$$[5,12]$$$ denoting the good pair itself.
Note that the two brackets making a good pair are always added on the same MBS, because otherwise it must make "contradicting informations".
If we can track the MBSes, split efficiently, and count the number of indices in the resulting MBSes, we can do the following to update the answer:
• When an MBS $$$S$$$ is split into three MBSes $$$A$$$, $$$B$$$ and the good pair, divide (multiply the inverse) the answer by $$$C_{|S|/2}$$$, and multiply the answer by $$$C_{|A|/2} \cdot C_{|B|/2}$$$. The Catalan number corresponding to the good pair is automatically $$$1$$$, so it does not matter.
To deal with the required operations, the model solution uses a forest of splay trees. A forest of splay trees is just a splay tree which does not specify a single root, so there can be multiple roots in the structure. In practice, a node is considered a root simply if it does not have a parent. Ideally, it is most convenient to implement it on a sequential data structure (e.g. vector) using indices than using pointers in this task, because you will need to access a node immediately given the index. It is possible to do the same using treaps, but some operations' implementation may be more convoluted if you use treaps.
You can notice that detecting if there exist subsequences inside or outside the good pair naturally translate to a series of simple operations on the splay tree, like follows:
• Detecting a subsequence inside: if there exists a subsequence inside the good pair $$$(l,r)$$$, you can splay the node $$$l$$$ and cut its right subtree. Now the right subtree will only contain values greater than $$$l$$$, so if you splay node $$$r$$$ on it, node $$$r$$$ will not have a left subtree if and only if there was no subsequence inside $$$(l,r)$$$. If there exists a subsequence inside, then the left child of $$$r$$$ is one element of the subsequence inside.
• Detecting a subsequence outside: if there exists a subsequence outside the good pair $$$(l,r)$$$, the tree will have values either less than $$$l$$$ or greater than $$$r$$$. In other words, if you splay node $$$l$$$ and find a left subtree, or splay node $$$r$$$ and find a right subtree, there exists a subsequence outside.
• Connecting the left and right subsequences: The left subtree of $$$l$$$ after it is splayed, and the right subtree of $$$r$$$ after it is splayed, might both have two children. If that is the case, you can simply find the leftmost node in the right subtree of $$$r$$$ and splay it, and then connect the left subtree of $$$l$$$ to its left. (This is only just a simple binary search tree operation.)
• Counting the subsequence sizes after the split: This is simple; we already found at least one node corresponding to each of the two subsequences. Splay the two nodes and find the size of the trees.
Now the only thing left in the solution is careful implementation. The solution has an amortized time complexity of $$$\mathcal{O}(n \log n)$$$, and runs comfortably in $$$1$$$ second.
Though the model solution used a complex data structure to utilize its convenient characteristics, the author acknowledges that it is possible to replace some details or entire sections of the editorial with other data structures or techniques such as segment trees or a smaller-to-larger trick. If you can prove that your solution works in $$$\mathcal{O}(n \log n)$$$ time complexity with a not too terrible constant, your solution is deemed to be correct.