Light Bulbs (Hard Version) (Codeforces 1914G2)
Tags: DP, 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: 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: 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$$$). 


Sample Inputs:
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

Sample Outputs:
2 4
1 2
1 4
2 8

Solution (Python):
import random
import math
t = int(input())
MOD = 998244353
MAX = int(math.pow(2, 64))
random.seed(1)

def g2(a, n):
    left = list()
    right = list()
    l_r = list()
    val = [0] * (n + 1)
    for i in range(1, len(val)):
        val[i] = gen()
    cur = 0
    last = dict()
    last[0] = -1
    for i in range(n * 2):
        cur = cur ^ val[a[i]]
        if last.get(cur) is not None:
            l_r.append((last.get(cur) + 1, i))
            last[cur] = i
        else:
            last[cur] = i
    l_r.sort()
    (left, right) = zip(*l_r)
    return (left, right)

def gen():
    return random.randint(1, MAX)
for _i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    (left, right) = g2(a, n)
    left_uncrossed = list()
    right_uncrossed = list()
    left_point = 0
    left_uncrossed.append(left[0])
    right_uncrossed.append(right[0])
    while True:
        if left_point == len(left):
            break
        if left[left_point] == right_uncrossed[len(right_uncrossed) - 1] + 1:
            left_uncrossed.append(left[left_point])
            right_uncrossed.append(right[left_point])
        left_point += 1
    point_crossed = -1
    is_good_lit = [True] * 2 * n
    for i in range(len(left_uncrossed)):
        left_bound = left_uncrossed[i]
        right_bound = right_uncrossed[i]
        while True:
            point_crossed += 1
            if point_crossed == len(left):
                break
            left_to_check = left[point_crossed]
            right_to_check = right[point_crossed]
            if left_to_check == left_bound and right_to_check == right_bound:
                continue
            if left_to_check > right_bound:
                break
            if left_to_check < right_bound and right_to_check <= right_bound:
                for j in range(left_to_check, right_to_check + 1):
                    is_good_lit[j] = False
    prefix_sum = [0] * n * 2
    prefix_sum[0] = int(is_good_lit[0])
    for i in range(1, n * 2):
        prefix_sum[i] = prefix_sum[i - 1] + int(is_good_lit[i])
    ans = 1
    for i in range(len(left_uncrossed)):
        left_bound = left_uncrossed[i]
        right_bound = right_uncrossed[i]
        cur = prefix_sum[right_bound] - prefix_sum[left_bound] + int(is_good_lit[left_bound])
        ans = ans * cur % MOD
    print(len(left_uncrossed), ans)

Solution (Python):
import sys
import io
import os
from string import *
from re import *
from collections import *
from heapq import *
from bisect import *
from copy import *
from random import *
from itertools import *
from functools import *
from operator import *
from typing import *
MOD = 998244353

def solve():
    n = read_int()
    A = read_ints_minus_one()
    covered = [[] for _ in range(n)]
    (stk, groups, c) = ([], [], [0] * n)
    for x in A:
        if stk and stk[-1] != x:
            covered[x].append(stk[-1])
        c[x] += 1
        if c[x] == 1:
            if not stk:
                groups.append(x)
            stk.append(x)
        while stk and c[stk[-1]] == 2:
            stk.pop()
    res = 1
    for u in groups:
        (q, cc) = (deque([u]), 1)
        seen = {u}
        while q:
            u = q.popleft()
            for x in covered[u]:
                if x not in seen:
                    q.append(x)
                    seen.add(x)
                    cc += 1
        res = res * cc * 2 % MOD
    print(len(groups), res)

def main():
    T = 1
    T = read_int()
    for t in range(T):
        solve()
BUFSIZE = 8192

class FastIO(io.IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int_list():
    return list(map(int, input().split()))

def read_ints_minus_one():
    return [int(x) - 1 for x in input().split()]

def read_int_tuple():
    return map(int, input().split())

def read_encode_str(d=97):
    return [ord(x) - d for x in input()]

def read_graph(n: int, m: int, d=1):
    g = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        g[u - d].append(v - d)
        g[v - d].append(u - d)
    return g

def read_grid(m: int):
    return [input() for _ in range(m)]

def read_int():
    return int(input())
read_str = input
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from random import randint
    vi = set()
    hash_ = [0] * 200005
    max_long_long = (1 << 63) - 1
    for i in range(1, 200005):
        while True:
            hs = randint(1, max_long_long)
            if hs not in vi:
                hash_[i] = hs
                vi.add(hs)
                break
    ''
    mod = 998244353
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        c = readIntArr()
        for i in range(2 * n):
            c[i] = hash_[c[i]]
        vi = set()
        open_cnts = 0
        hash_cnts = dict()
        hash_cnts[0] = 0
        XOR = 0
        ans1 = 0
        ans2 = 1
        for x in c:
            XOR ^= x
            if x not in vi:
                vi.add(x)
                open_cnts += 1
            elif XOR in hash_cnts.keys():
                group_size = open_cnts - hash_cnts[XOR]
                open_cnts -= group_size
                if open_cnts == 0:
                    ans1 += 1
                    ans2 = ans2 * group_size * 2 % mod
            hash_cnts[XOR] = open_cnts
        allans.append((ans1, ans2))
    multiLineArrayOfArraysPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()