Light Bulbs (Hard Version)
Contest: Codeforces Round 916 (Div. 3)
Difficulty rating: 2300
Tags: combinatorics, data structures, dfs and similar, dp, graphs, hashing

The easy and hard versions of this problem differ only in the constraints on $$$n$$$. In the hard version, the sum of values of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. Furthermore, there are no additional constraints on the value of $$$n$$$ in a single test case.

There are $$$2n$$$ light bulbs arranged in a row. Each light bulb has a color from $$$1$$$ to $$$n$$$ (exactly two light bulbs for each color).

Initially, all light bulbs are turned off. You choose a set of light bulbs $$$S$$$ that you initially turn on. After that, you can perform the following operations in any order any number of times:

- choose two light bulbs $$$i$$$ and $$$j$$$ of the same color, exactly one of which is on, and turn on the second one;
- choose three light bulbs $$$i, j, k$$$, such that both light bulbs $$$i$$$ and $$$k$$$ are on and have the same color, and the light bulb $$$j$$$ is between them ($$$i < j < k$$$), and turn on the light bulb $$$j$$$.

You want to choose a set of light bulbs $$$S$$$ that you initially turn on in such a way that by performing the described operations, you can ensure that all light bulbs are turned on.

Calculate two numbers:

- the minimum size of the set $$$S$$$ that you initially turn on;
- the number of sets $$$S$$$ of minimum size (taken modulo $$$998244353$$$).

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of pairs of light bulbs.

The second line of each test case contains $$$2n$$$ integers $$$c_1, c_2, \dots, c_{2n}$$$ ($$$1 \le c_i \le n$$$), where $$$c_i$$$ is the color of the $$$i$$$-th light bulb. For each color from $$$1$$$ to $$$n$$$, exactly two light bulbs have this color.

Additional constraint on the input: the sum of values of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output two integers:

- the minimum size of the set $$$S$$$ that you initially turn on;
- the number of sets $$$S$$$ of minimum size (taken modulo $$$998244353$$$).

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

Example input:
4
2
2 2 1 1
2
1 2 2 1
2
1 2 1 2
5
3 4 4 5 3 1 1 5 2 2

Example output:
2 4
1 2
1 4
2 8

Editorial:
Let's call a contiguous segment of lamps closed if the number of lamps for each color is either $$$0$$$ or $$$2$$$ in this segment. For example, a segment of lamps $$$[3, 2, 1, 2, 1, 3]$$$ is closed. Furthermore, let's say that a closed segment of lamps is minimal if it is impossible to split it into multiple closed segments. For example, $$$[3, 2, 1, 2, 1, 3]$$$ is minimal, but $$$[3, 3, 2, 1, 2, 1]$$$ is not since it can be split into $$$[3, 3]$$$ and $$$[2, 1, 2, 1]$$$ (which are closed).
Each closed segment has the following property: if you start with any lamp in this segment, you cannot "leave" this segment; i. e. you cannot use the lamps from this segment to light any lamps outside. To prove this, let's suppose the opposite: we started in the closed segment and managed to turn a lamp of color $$$x$$$ outside that segment on (and this was the first lamp outside of the segment we turned on). We could not do it with the operation of the first type, since it would mean that the other lamp of color $$$x$$$ is in the segment (so it is not closed); and we could not do it with the operation of the second type, since for every color present in the closed segment, both lamps of that color (and the segment they can light up) belong to the closed segment.
For every minimal closed segment, we can light it up using just one lamp (for example, the first lamp). So, to calculate the minimum possible size of a set of lamps $$$S$$$ we initially turn on, we can just split the given sequence of colors into minimal closed segments.
Unfortunately, calculating the number of possible sets of lamps $$$S$$$ is trickier. For every minimal closed segment we got, we can calculate the number of "starting" lamps that allow us to light the whole segment, and multiply them. However, not every lamp from a minimal closed segment can be a "starting" lamp: for example, in the segment $$$[3, 2, 1, 2, 1, 3]$$$, any lamp of color $$$3$$$ can be used, but no lamp of other color can be used.
To deal with this, let us find all minimal closed segments in the sequence of colors. In the example above, we have to find out that both the segments $$$[3, 2, 1, 2, 1, 3]$$$ and $$$[2, 1, 2, 1]$$$ are closed; and since lamps of colors $$$1$$$ and $$$2$$$ belong to the "inner" closed segment, they cannot be used to light the whole "outer" closed segment. So, if a lamp belongs to any of the "inner" closed segments, it cannot be used as a starting lamp. Let's mark all such lamps.
We can also show that if a lamp is not marked, it can be used as a starting lamp. It is because if we start with some lamp and try to turn on everything we can with the operations given in the statement, we will get precisely the shortest closed segment that lamp belongs to. Proving it is not that hard: suppose we stopped before turning the whole shortest closed segment on; either we got multiple segments of lamps (and we can turn on everything in between them), or we got a segment which is not closed (and for at least one color, there is exactly one lamp in it; so we can light the other lamp of that color).
Okay, let's recap. Our solution consists of the following steps:
• find all minimal closed segments of lamps;
• for every "inner" segment, mark all lamps in it to show they cannot be used as the starting lamps;
• split the given sequence of colors into the minimum number of segments;
• for each segment we got from the split, calculate the number of unmarked lamps and multiply those values.
The most difficult part is finding all minimal closed segments of lamps. To get a solution in something like $$$O(n^2)$$$, we can do it naively: iterate on the left border of the segment, add the first lamp in the segment, and keep adding next lamps until the number of lamps of each color becomes either $$$0$$$ or $$$2$$$. That's how the easy version of the problem is solved.
For the hard version, this is too slow. We have to find the closed segments faster. In order to do this, we can use hashing. Many hashing methods can help, but in my opinion, the most elegant one is XOR hashing, which works as follows:
For each color, generate a random $$$64$$$-bit integer and replace both occurrences of that color with the generated number. Then, if the segment is closed, the XOR of all numbers in the segment is equal to $$$0$$$ (each color occurs either $$$0$$$ or $$$2$$$ times, thus each integer is taken either $$$0$$$ or $$$2$$$ times, and all integers taken twice cancel out).
This allows us to find all minimal closed segments in $$$O(n \log n)$$$ as follows: iterate on the array of colors from left to right, maintaining the XOR on the current prefix and a map where, for each XOR we encountered, we store the longest prefix which has that value of XOR. Then, after we process the $$$i$$$-th element, we can quickly find the left border of the segment ending in the $$$i$$$-th element by looking for the current XOR in the map. Don't forget to update the map after that.
That way, we arrive at a solution which works in $$$O(n \log n)$$$, which is enough to solve the hard version.