AtCoder Regular Contest++ 216 A,B,C問題メモ

from sortedcontainers import SortedSet

def solve(n, a, b):
    aaa = list(map(int, a))
    bbb = list(map(int, b))
    if aaa[0] != bbb[0] or aaa[-1] != bbb[-1]:
        return -1
    ccc = [aaa[i] ^ aaa[i + 1] for i in range(n - 1)]
    ddd = [bbb[i] ^ bbb[i + 1] for i in range(n - 1)]
    ddd = [ccc[0] ^ 1] + ddd + [ccc[-1] ^ 1]
    ccc = [ccc[0] ^ 1] + ccc + [ccc[-1] ^ 1]
    aaa = [ccc[i] ^ ccc[i + 1] for i in range(n)]
    bbb = [ddd[i] ^ ddd[i + 1] for i in range(n)]
    idx = SortedSet(i for i, a in enumerate(aaa) if a == 0)
    ans = 0
    for i in range(n):
        if aaa[i] == bbb[i]:
            continue
        ji = idx.bisect(i)
        if ji == len(idx):
            return -1
        j = idx[ji]
        if j == n - 1:
            return -1
        aaa[i] ^= 1
        aaa[j + 1] ^= 1
        ans += j - i
        if i + 1 < j:
            aaa[i + 1] = 0
            aaa[j] = 1
            idx.remove(j)
        if aaa[j + 1] == 0:
            idx.add(j + 1)
        else:
            idx.remove(j + 1)
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    a = input()
    b = input()
    ans = solve(n, a, b)
    print(ans)

from bisect import bisect
from operator import add

from atcoder.segtree import SegTree


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, q, aaa, queries):
    not_used = [True] * n
    acc_min_left = [n] * (n + 1)
    acc_min_right = [n] * (n + 1)
    sgt2 = SegTree(add, 0, n)
    for i, a in enumerate(aaa):
        if a == -1:
            sgt2.set(i, 1)
            continue
        not_used[a] = False
        acc_min_left[i + 1] = a
        acc_min_right[i] = a
    not_used = [a for a, u in enumerate(not_used) if u]
    m = len(not_used)
    not_used.append(n)

    for i in range(1, n + 1):
        acc_min_left[i] = min(acc_min_left[i - 1], acc_min_left[i])
    for i in range(n - 1, -1, -1):
        acc_min_right[i] = min(acc_min_right[i], acc_min_right[i + 1])

    MOD = 998244353
    facts, finvs = precompute_factorials(m, MOD)
    invs = [1]
    for i in range(1, m + 1):
        invs.append(finvs[i] * facts[i - 1] % MOD)

    precalc1 = [[0]]  # 区間中の-1の個数 x 毎に、(mex が not_used[i] になる確率) * (not_used[i]) の累積和
    precalc2 = [[0]]  # 区間中の-1の個数 x 毎に、(mex が not_used[i] になる確率) の累積和
    for x in range(1, m + 1):
        pc1 = [0]
        pc2 = [0]
        p = 1
        for i in range(x + 1):
            tmp = p * (m - x) * invs[m - i] % MOD
            pc1.append((pc1[-1] + tmp * not_used[i]) % MOD)
            pc2.append((pc2[-1] + tmp) % MOD)
            p = p * (x - i) * invs[m - i] % MOD
        precalc1.append(pc1)
        precalc2.append(pc2)
        # print(f'{x=} {precalc1=}')
        # print(f'{x=} {precalc2=}')
    # print(f'{not_used=}')

    buf = []
    for l, r in queries:
        l -= 1
        min1 = acc_min_left[l]
        min2 = acc_min_right[r]
        k = min(min1, min2)
        # print(f'{l=} {r=} {k=} {buf=}')

        if m == 0:
            buf.append(k)
            continue

        bi = bisect(not_used, k)
        if bi == 0:
            ans = k * facts[m] % MOD
            buf.append(ans)
            continue

        x = sgt2.prod(l, r)
        if x == 0:
            ans = not_used[0] * facts[m] % MOD
            buf.append(ans)
            continue

        if x == m:
            ans = k * facts[m] % MOD
            buf.append(ans)
            continue

        if x < bi:
            ans = precalc1[x][x]
            ans += (1 - precalc2[x][x]) * not_used[x]
            ans *= facts[m]
            ans %= MOD
            buf.append(ans)
            continue

        # print(f'{not_used=} {x=} {k=} {bi=}')
        ans = precalc1[x][bi]
        ans += (1 - precalc2[x][bi]) * k
        ans *= facts[m]
        ans %= MOD
        buf.append(ans)

    return buf


n, q = list(map(int, input().split()))
aaa = list(map(int, input().split()))
queries = [list(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, aaa, queries)
print('\n'.join(map(str, ans)))

from bisect import bisect_left, bisect
from collections import defaultdict

M = 5
MODS = [999999893, 999999929, 1000000021, 1000000033, 1000000087, ]
S_BASE = 37
S_MOD = 1000000000000037

POW2S = []
for mod in MODS:
    tmp = [1]
    for _ in range(200_100):
        tmp.append(tmp[-1] * 2 % mod)
    POW2S.append(tmp)


def build_cartesian_tree(n, op):
    """ Cartesian Tree の構築

    左から 0,1,...,N-1 の頂点番号で表し、以下を構築して返す。
    root: 根の頂点番号
    left[i] := i の左の子の頂点番号、存在しない場合は-1
    right[i] := i の右の子の頂点番号、存在しない場合は-1
    parents[i] := i の親の頂点番号、存在しない場合は-1

    op: 2つの頂点番号 (i,j) を引数に取り、i < j（Cartesian Tree で i が親になるべき）なら True を返す関数。
    """
    stack = []
    root = 0
    left = [-1] * n
    right = [-1] * n
    parents = [-1] * n
    for i in range(n):
        last_popped = -1
        while stack and op(i, stack[-1]):
            last_popped = stack.pop()
        if last_popped != -1:
            left[i] = last_popped
            parents[last_popped] = i
        if len(stack) == 0:
            root = i
        else:
            parents[i] = stack[-1]
            right[stack[-1]] = i
        stack.append(i)
    return root, left, right, parents


def solve(n, aaa):
    accs = []
    for j in range(M):
        acc = [0]
        for i in range(n):
            acc.append((acc[-1] + POW2S[j][aaa[i]]) % MODS[j])
        accs.append(acc)

    # print(f'{accs=}')

    # 3つのaccの組をキーとし、衝突を回避

    def get_key(i, accs):
        x = 0
        for j in range(M):
            x *= S_BASE
            x += accs[j][i]
            x %= S_MOD
        return x

    def get_key2(i, c, accs):
        x = 0
        for j in range(M):
            x *= S_BASE
            x += (accs[j][i] + POW2S[j][c]) % MODS[j]
            x %= S_MOD
        return x

    def get_key3(i, c, accs):
        x = 0
        for j in range(M):
            x *= S_BASE
            y = (accs[j][i] - POW2S[j][c]) % MODS[j]
            if y < 0:
                y += MODS[j]
            x += y
            x %= S_MOD
        return x

    acc_pos = defaultdict(list)
    for i in range(n + 1):
        acc_pos[get_key(i, accs)].append(i)
    acc_pos = dict(acc_pos)

    # print(f'{acc_pos=}')

    def op(i, j):
        if aaa[i] > aaa[j]:
            return True
        if aaa[i] < aaa[j]:
            return False
        return i < j

    root, left, right, parents = build_cartesian_tree(n, op)

    def divide_conquer(i, l, r):
        a = aaa[i]
        ans = 0
        if i - l < r - i:
            for j in range(l, i + 1):
                for c in range(a, a + 22):
                    target = get_key2(j, c, accs)
                    if target in acc_pos:
                        pi = bisect(acc_pos[target], i)
                        pj = bisect(acc_pos[target], r)
                        # print(f'{i=} {l=} {r=} L {j=} {a=} {c=} {pi=} {pj=}')
                        ans += pj - pi
        else:
            for j in range(i + 1, r + 1):
                for c in range(a, a + 22):
                    target = get_key3(j, c, accs)
                    if target in acc_pos:
                        pi = bisect_left(acc_pos[target], l)
                        pj = bisect(acc_pos[target], i)
                        # print(f'{i=} {l=} {r=} R {j=} {a=} {c=} {pi=} {pj=}')
                        ans += pj - pi
        # print(f'{i=} {l=} {r=} {aaa[i]=} {ans=}')
        lc = left[i]
        rc = right[i]
        if lc != -1:
            ans += divide_conquer(lc, l, i)
        if rc != -1:
            ans += divide_conquer(rc, i + 1, r)
        return ans

    ans = divide_conquer(root, 0, n)
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
print(ans)