Lexichromatography (Codeforces 1876D)
Tags: Others, dsu

Pak Chanek loves his faculty, the Faculty of Computer Science, University of Indonesia (Fasilkom). He wants to play with the colours of the faculty's logo, blue and red.There is an array $$$a$$$ consisting of $$$n$$$ elements, element $$$i$$$ has a value of $$$a_i$$$. Pak Chanek wants to colour each element in the array blue or red such that these following conditions are satisfied:   If all blue elements are formed into a subsequence$$$^\dagger$$$ and so are all the red elements, the blue subsequence is strictly less than the red subsequence lexicographically$$$^\ddagger$$$.  Array $$$a$$$ does not have any subarray that is imbalanced. A subarray is imbalanced if and only if there is a value $$$k$$$ such that the absolute difference between the number of blue elements with value $$$k$$$ and the number of red elements with value $$$k$$$ in this subarray is $$$2$$$ or more.  Note that it is possible to colour every element of the array the same colour. How many different colourings satisfy all those conditions? Since the answer can be very big, print the answer modulo $$$998\,244\,353$$$. Two colourings are different if and only if there is at least one element that is blue in one colouring, but red in the other.$$$^\dagger$$$ A subsequence of an array is a sequence that can be obtained from the array by deleting some elements (possibly none), without changing the order of the remaining elements.$$$^\ddagger$$$ Let $$$p$$$ and $$$q$$$ be two different sequences. Sequence $$$p$$$ is said to be lexicographically less than sequence $$$q$$$ if and only if $$$p$$$ is a prefix of $$$q$$$ or there is an index $$$i$$$ such that $$$p_j=q_j$$$ holds for every $$$1\leq j<i$$$, and $$$p_i<q_i$$$. In particular, an empty sequence is always lexicographically less than any non-empty sequence.

Input: The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the size of array $$$a$$$.The second line contains $$$n$$$ integers $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1\leq a_i\leq2\cdot10^5$$$).

Output: An integer representing the number of different colourings that satisfy all of the problem's conditions, modulo $$$998\,244\,353$$$.

Note: In the first example, the $$$3$$$ ways for colouring all elements from index $$$1$$$ to index $$$8$$$ are:   Blue, red, red, blue, blue, red, red, blue.  Blue, red, red, red, blue, blue, red, blue.  Red, red, blue, blue, blue, red, red, blue. As an example, if we colour the elements from index $$$1$$$ to index $$$8$$$ to be red, red, blue, red, red, blue, blue, blue, it is not valid colouring, because for subarray $$$a[2..6]$$$, there are $$$0$$$ blue elements with value $$$3$$$ and $$$2$$$ red elements with value $$$3$$$, making subarray $$$a[2..6]$$$ an imbalanced subarray.

Sample Inputs:
8
1 3 1 2 3 2 3 3

1
265

Sample Outputs:
3

1

Solution (Python):
(standard_input, packages, output_together) = (1, 1, 0)
(dfs, hashing, read_from_file) = (0, 0, 0)
de = 1
if 1:
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().strip()
        import math
        inf = math.inf

        def I():
            return input()

        def II():
            return int(input())

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

        def LI():
            return list(input().split())

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

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import merge, heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        class FastIO(IOBase):
            newlines = 0

            def __init__(self, file):
                self._fd = file.fileno()
                self.buffer = 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(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')
        sys.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        def bootstrap(f, stack=[]):

            def wrappedfunc(*args, **kwargs):
                if stack:
                    return f(*args, **kwargs)
                else:
                    to = f(*args, **kwargs)
                    while True:
                        if type(to) is GeneratorType:
                            stack.append(to)
                            to = next(to)
                        else:
                            stack.pop()
                            if not stack:
                                break
                            to = stack[-1].send(to)
                    return to
            return wrappedfunc
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args, **kwargs):
            print('\x1b[92m', end='')
            print(*args, **kwargs)
            print('\x1b[0m', end='')

class UnionFind:

    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        a = self.parent[a]
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            (self.parent[acopy], acopy) = (a, self.parent[acopy])
        return a

    def merge(self, a, b):
        (pa, pb) = (self.find(a), self.find(b))
        if pa == pb:
            return False
        self.parent[pb] = pa
        return True
mod = 998244353
n = II()
nums = LGMI()
cnt = [0] * (2 * 10 ** 5)
for num in nums:
    cnt[num] += 1
ans = 1
for v in cnt:
    if v:
        ans *= 2
        ans %= mod
ans *= (mod + 1) // 2
ans %= mod
for x in cnt:
    if x % 2:
        print(ans)
        exit()
pos = [-1] * (2 * 10 ** 5)
segs = [-1] * n
for i in range(n):
    if pos[nums[i]] == -1:
        pos[nums[i]] = i
    else:
        segs[i] = pos[nums[i]]
        pos[nums[i]] = -1
cur = -1
for i in range(n):
    if cur >= segs[i] and segs[i] != -1:
        print(ans)
        exit()
    cur = max(cur, segs[i])
union = UnionFind(2 * 10 ** 5)
cnt = sum((1 for x in cnt if x)) - 1
last = -1
for i in range(n):
    if segs[i] != -1:
        if last == -1:
            last = i
        else:
            if segs[i] < last:
                cnt -= union.merge(nums[i], nums[last])
            last = i
print((ans - pow(2, cnt, mod)) % mod)

Solution (Python):
from sys import *
from collections import deque
input = stdin.readline
inputlist = lambda : map(int, stdin.readline().split())
MOD = 998244353

def solve():
    n = int(input())
    array = list(inputlist())
    valuedict = {}
    for value in array:
        if value in valuedict:
            valuedict[value] += 1
        else:
            valuedict[value] = 1
    for count in valuedict.values():
        if count % 2:
            return pow(2, len(valuedict) - 1, MOD)
    visited = {array[0]}
    currentset = set([array[0]])
    current = deque([array[0]])
    arrays = []
    temparray = [array[0]]
    for value in array[1:]:
        if len(current) == 0:
            arrays.append(temparray)
            temparray = []
        if value in visited:
            if value in currentset:
                if value != current[0]:
                    return pow(2, len(valuedict) - 1, MOD)
                else:
                    current.popleft()
                    currentset.discard(value)
            else:
                current.append(value)
                currentset.add(value)
                temparray.append(value)
        else:
            current.append(value)
            currentset.add(value)
            visited.add(value)
            temparray.append(value)
    if len(current) == 0:
        arrays.append(temparray)
    visited = [0] * 200001
    numtoindex = [[] for _ in range(200001)]
    for (index, array) in enumerate(arrays):
        for value in array:
            numtoindex[value].append(index)
            visited[value] = 1
    count = 0
    current = set()
    for i in range(1, 200001):
        if visited[i]:
            count += 1
            current = set([i])
            while current:
                newcurrent = set()
                for i in current:
                    visited[i] = 0
                newnums = set()
                for i in current:
                    for indices in numtoindex[i]:
                        newnums.add(indices)
                for indices in newnums:
                    for num in arrays[indices]:
                        if visited[num]:
                            newcurrent.add(num)
                current = newcurrent
    return (pow(2, len(valuedict) - 1, MOD) - pow(2, count - 1, MOD)) % MOD
print(solve())

Solution (Python):
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
M = 2 * 10 ** 5 + 100
mod = 998244353

def brute(N, A):
    first = [-1] * M
    last = [-1] * M
    k = 0
    val = []
    for (i, a) in enumerate(A):
        if first[a] == -1:
            k += 1
            first[a] = i
            val.append(a)
        last[a] = i
    ans = 0
    for S in range(1 << k):
        next_color = [''] * M
        for i in range(k):
            if S >> i & 1:
                next_color[val[i]] = 'r'
            else:
                next_color[val[i]] = 'b'
        tmp_r = []
        tmp_b = []
        for a in A:
            if next_color[a] == 'r':
                tmp_r.append(a)
                next_color[a] = 'b'
            else:
                tmp_b.append(a)
                next_color[a] = 'r'
        if tmp_r < tmp_b:
            ans += 1
    return ans

def solve(N, A):
    A = [a - 1 for a in A]
    first = [-1] * M
    last = [-1] * M
    k = 0
    for (i, a) in enumerate(A):
        if first[a] == -1:
            k += 1
            first[a] = i
        last[a] = i
    same = 1
    tmp_red = []
    tmp_blue = []
    next_color = ['' for i in range(M)]
    tmp_last = -1
    group = [[x] for x in range(M)]
    x_to_g = [x for x in range(M)]
    maxi_last = [last[x] for x in range(M)]
    for i in range(N):
        a = A[i]
        if next_color[a] == '':
            tmp_red.append(a)
            next_color[a] = 'b'
        elif next_color[a] == 'r':
            tmp_red.append(a)
            next_color[a] = 'b'
        else:
            if tmp_red[len(tmp_blue)] != a:
                same = 0
                break
            tmp_blue.append(a)
            next_color[a] = 'r'
        if len(tmp_red) == len(tmp_blue):
            root = x_to_g[tmp_red[0]]
            for x in tmp_red[1:]:
                rx = x_to_g[x]
                if rx == root:
                    continue
                if len(group[root]) < len(group[rx]):
                    for val in group[root]:
                        group[rx].append(val)
                        maxi_last[rx] = max(maxi_last[rx], last[val])
                        x_to_g[val] = rx
                    group[root] = []
                    root = rx
                else:
                    for val in group[rx]:
                        group[root].append(val)
                        maxi_last[root] = max(maxi_last[root], last[val])
                        x_to_g[val] = root
                    group[rx] = []
            check = 0
            for x in tmp_red:
                if i < maxi_last[x_to_g[x]]:
                    check = 1
                next_color[x] = ''
            if check == 0:
                same = 2 * same
                same %= mod
            (tmp_red, tmp_blue) = ([], [])
    if tmp_red != tmp_blue:
        same = 0
    res = pow(2, k, mod) - same
    res *= pow(2, mod - 2, mod)
    res %= mod
    return res
while False:
    N = 12
    A = []
    for i in range(N // 2):
        a = random.randint(1, N // 2)
        A.append(a)
        A.append(a)
    random.shuffle(A)
    if solve(N, A) != brute(N, A):
        print(N)
        print(A)
        print(solve(N, A), brute(N, A))
        exit()
    assert solve(N, A) == brute(N, A)
    print('AC', solve(N, A))
N = int(input())
A = li()
print(solve(N, A))