AtCoder Beginner Contest 418 C,D,E,F問題メモ

from collections import Counter, defaultdict


def solve(n, q, aaa, difficulties):
    queries = defaultdict(list)
    for qi, b in enumerate(difficulties):
        queries[b].append(qi)
    ans = [-1] * q

    cnt = Counter(aaa)
    impossible_max = 0
    rem = n
    for i in range(1, max(aaa) + 1):
        if i in queries:
            for qi in queries[i]:
                ans[qi] = impossible_max + 1
        impossible_max += rem
        if i in cnt:
            rem -= cnt[i]
    return ans


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

def solve(n, t):
    cnt = [1, 0, 0, 0]  # (偶数indexで累積和%2=0, 偶数/1, 奇数/0, 奇数/1)  の個数
    acc = 0
    for i, c in enumerate(map(int, t), start=1):
        acc ^= c
        cnt[(i % 2) << 1 | acc] += 1
    ans = 0
    for i in range(4):
        ans += cnt[i] * (cnt[i] - 1) // 2
    ans += cnt[0] * cnt[3] + cnt[1] * cnt[2]
    return ans


n = int(input())
t = input()
ans = solve(n, t)
print(ans)

from collections import defaultdict, Counter
from math import gcd


def solve(n, points):
    cnt = defaultdict(list)
    for i in range(n):
        x1, y1 = points[i]
        for j in range(i + 1, n):
            x2, y2 = points[j]
            dx = x2 - x1
            dy = y2 - y1
            if dx < 0:
                dx *= -1
                dy *= -1
            if dx == 0 and dy < 0:
                dy *= -1
            g = gcd(dx, abs(dy))
            dx //= g
            dy //= g
            cnt[dx, dy].append(g)

    ans = 0
    parallelogram = 0
    for ls in cnt.values():
        c = len(ls)
        ans += c * (c - 1) // 2
        for gc in Counter(ls).values():
            parallelogram += gc * (gc - 1) // 2
    ans -= parallelogram // 2

    return ans


n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, points)
print(ans)

import sys


class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木

    [生成]
    SegmentTreeInjectable(n, identity, func)
    SegmentTreeInjectable.from_array(array, identity, func)  # 既存の配列より作成

    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """

    def __init__(self, n, identity, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.identity = identity
        self.tree = [identity] * (n2 << 1)
        self.func = func

    @classmethod
    def from_array(cls, arr, identity, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins

    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)

    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)

    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])

    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.identity
        result_r = self.identity

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return func(result_l, result_r)

    def get_all(self):
        return self.tree[1]

    def get_point(self, i):
        return self.tree[i + self.offset]

    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1

        if r_found == -1:
            return -1

        return self._leftmost_sub(r_found, x, ev)

    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset

    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1

        if l_found == -1:
            return -1

        return self._rightmost_sub(l_found, x, ev)

    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1


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, queries):
    MOD = 998244353
    facts, finvs = precompute_factorials(n + 1, MOD)

    def calc_pattern(n, m):
        # n個のカップからm個に珈琲入れる → n-m 個の紅茶の隙間 n-m+1 個に珈琲を挿入する
        if m == 0:
            return 1
        if m < 0:
            return 0
        if n - m + 1 < m:
            return 0
        return facts[n - m + 1] * finvs[m] % MOD * finvs[n - m + 1 - m] % MOD

    # 個数制限無しはフィボナッチ
    all_free = [1, 2]
    for i in range(n):
        all_free.append((all_free[i] + all_free[i + 1]) % MOD)

    def merge(a, b):
        #  0        1                      2        3
        # (左の制限, 左の制限からの自由マス数, 右の制限, 右の制限からの自由マス数,    であって、
        #  4                 5   6   7      8
        #  左右の制限マスが00, 10, 01, 11, 全て-1フラグ)    の時の、制限に挟まれたマスのパターン数
        if a[8] == 1:
            if b[8] == 1:
                return (-1, a[1] + b[1], -1, a[3] + b[3], 0, 0, 0, 0, 1)
            return (b[0], a[1] + b[1], b[2], b[3], b[4], b[5], b[6], b[7], b[8])
        if b[8] == 1:
            return (a[0], a[1], a[2], a[3] + b[3], a[4], a[5], a[6], a[7], a[8])
        space = a[3] + b[1]
        coffee = b[0] - a[2]
        p00 = calc_pattern(space, coffee)
        p01 = calc_pattern(space - 1, coffee - 1)
        p10 = calc_pattern(space - 1, coffee)
        p11 = calc_pattern(space - 2, coffee - 1) if space >= 1 else 0
        # print(f'  {a=} {b=} {p00=} {p01=} {p10=} {p11=}')
        # print(f'    {a[3]+b[1]=} {b[0]-a[2]=}')
        return (
            a[0], a[1], b[2], b[3],
            (a[4] * p00 % MOD * b[4] + a[4] * p01 % MOD * b[5] +
             a[6] * p10 % MOD * b[4] + a[6] * p11 % MOD * b[5]) % MOD,  # 00
            (a[5] * p00 % MOD * b[4] + a[5] * p01 % MOD * b[5] +
             a[7] * p10 % MOD * b[4] + a[7] * p11 % MOD * b[5]) % MOD,  # 10
            (a[4] * p00 % MOD * b[6] + a[4] * p01 % MOD * b[7] +
             a[6] * p10 % MOD * b[6] + a[6] * p11 % MOD * b[7]) % MOD,  # 01
            (a[5] * p00 % MOD * b[6] + a[5] * p01 % MOD * b[7] +
             a[7] * p10 % MOD * b[6] + a[7] * p11 % MOD * b[7]) % MOD,  # 11
            0
        )

    init = [(-1, 1, -1, 1, 0, 0, 0, 0, 1)] * n
    sgt = SegmentTreeInjectable.from_array(init, (-1, 0, -1, 0, 0, 0, 0, 0, 1), merge)
    ans = []
    for x, y in queries:
        x -= 1
        if y == -1:
            sgt.update(x, (-1, 1, -1, 1, 0, 0, 0, 0, 1))
        else:
            sgt.update(x, (y, 0, y, 0, 1, 0, 0, 1, 0))
        res = sgt.get_all()
        # print(f'{x=} {y=} {res=}')
        # sgt.debug_print()

        if res[8] == 1:
            ans.append(all_free[n])
            continue

        tmp = 0
        l0 = calc_pattern(res[1], res[0])
        l1 = calc_pattern(res[1] - 1, res[0] - 1)
        # print(f'  {l0=} {l1=} {all_free[res[3]]=} ')
        tmp += l0 * res[4] % MOD * all_free[res[3]]
        tmp += l1 * res[5] % MOD * all_free[res[3]]
        if res[3] == 0:
            r_pat = 1
        else:
            r_pat = all_free[res[3] - 1]
        tmp += l0 * res[6] % MOD * r_pat
        tmp += l1 * res[7] % MOD * r_pat
        tmp %= MOD

        ans.append(tmp)
    return ans


input = sys.stdin.buffer.readline
n, q = map(int, input().split())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, queries)
print('\n'.join(map(str, ans)))

# 正規表現 → DFA 変換部分は ChatGPT による

from collections import defaultdict

# ---------- Step 2: Shunting-yard ----------
prec = {'*': 3, '+': 3, '.': 2, '|': 1}  # '.' は連結演算


def to_rpn(regex):
    # 明示的に連結記号 '.' を挿入
    tokens = []
    prev = '~'
    for c in regex:
        if c in '01':
            if prev in '01)*+':
                tokens.append('.')
            tokens.append(c)
        elif c == '(':
            if prev in '01)*+':
                tokens.append('.')
            tokens.append(c)
        elif c in '*+|)':
            tokens.append(c)
        prev = c
    # Shunting-yard
    out, stack = [], []
    for t in tokens:
        if t in '01':
            out.append(t)
        elif t in prec:
            while stack and stack[-1] in prec and prec[stack[-1]] >= prec[t]:
                out.append(stack.pop())
            stack.append(t)
        elif t == '(':
            stack.append(t)
        elif t == ')':
            while stack[-1] != '(':
                out.append(stack.pop())
            stack.pop()
    while stack:
        out.append(stack.pop())
    return out


# ---------- Step 3: Thompson NFA ----------
class State:
    def __init__(self):
        self.edges = defaultdict(list)  # symbol -> [state]
        self.eps = []  # epsilon transitions


def nfa_concat(a, b):
    for s in a[1].eps:
        pass
    a[1].eps.append(b[0])
    return a[0], b[1]


def nfa_union(a, b):
    s, e = State(), State()
    s.eps += [a[0], b[0]]
    a[1].eps.append(e)
    b[1].eps.append(e)
    return s, e


def nfa_star(a):
    s, e = State(), State()
    s.eps += [a[0], e]
    a[1].eps += [a[0], e]
    return s, e


def nfa_plus(a):
    s1, e1 = a
    s, e = State(), State()
    s.eps.append(s1)
    e1.eps += [s1, e]
    return s, e


def nfa_symbol(c):
    s, e = State(), State()
    s.edges[c].append(e)
    return s, e


def build_nfa(rpn):
    stack = []
    for t in rpn:
        if t in '01':
            stack.append(nfa_symbol(t))
        elif t == '.':
            b = stack.pop()
            a = stack.pop()
            a[1].eps.append(b[0])
            stack.append((a[0], b[1]))
        elif t == '|':
            b = stack.pop()
            a = stack.pop()
            s, e = State(), State()
            s.eps += [a[0], b[0]]
            a[1].eps.append(e)
            b[1].eps.append(e)
            stack.append((s, e))
        elif t == '*':
            a = stack.pop()
            stack.append(nfa_star(a))
        elif t == '+':
            a = stack.pop()
            stack.append(nfa_plus(a))
    return stack[0]


# ---------- Step 4: NFA → DFA ----------
def epsilon_closure(states):
    stack = list(states)
    closure = set(states)
    while stack:
        s = stack.pop()
        for t in s.eps:
            if t not in closure:
                closure.add(t)
                stack.append(t)
    return closure


def move(states, symbol):
    res = set()
    for s in states:
        for t in s.edges.get(symbol, []):
            res.add(t)
    return res


def nfa_to_dfa(start, accept):
    start_set = frozenset(epsilon_closure({start}))
    dfa_states = {start_set: 0}
    dfa_trans = {}
    accept_ids = set()
    queue = [start_set]
    while queue:
        cur = queue.pop()
        cur_id = dfa_states[cur]
        for c in '01':
            ns = frozenset(epsilon_closure(move(cur, c)))
            if not ns:
                continue
            if ns not in dfa_states:
                dfa_states[ns] = len(dfa_states)
                queue.append(ns)
            dfa_trans[(cur_id, c)] = dfa_states[ns]
        if accept in cur:
            accept_ids.add(cur_id)
    return dfa_states, dfa_trans, 0, accept_ids


def regex_to_dfa(regex):
    rpn = to_rpn(regex)
    nfa_start, nfa_accept = build_nfa(rpn)
    dfa_states, dfa_trans, dfa_start, dfa_accepts = nfa_to_dfa(nfa_start, nfa_accept)

    dfa_trans_ = {}
    for (s, c), t in dfa_trans.items():
        if type(s) is int:
            dfa_trans_[s, c] = t
        else:
            dfa_trans_[dfa_states[s], c] = t
    dfa_trans = dfa_trans_
    # print(f'{regex=} {len(dfa_states)=}')

    return dfa_states, dfa_trans, dfa_start, dfa_accepts


def automaton(n, tr, accept, t):
    """
    n 状態のオートマトンで、初期状態は 0。

    Args:
        n: 状態数
        tr: 2次元の遷移先配列。tr[from, c] = from 状態から文字 c が来た場合の遷移先
        accept: 受理状態の状態番号の set
        t: 検索対象文字列（0,1 のみなので、int配列に変換済みの前提）

    Returns: (文字列 t の中で受理状態となる最も長い部分文字列の長さ, 受理状態となる部分文字列数)

    """

    max_len = [-1] * n
    state_count = [0] * n
    maximum_len = -1
    total_count = 0
    for c in t:
        nml = [-1] * n
        nsc = [0] * n
        for from_ in range(n):
            if state_count[from_] == 0:
                continue
            if (from_, c) in tr:
                to = tr[from_, c]
                nml[to] = max(nml[to], max_len[from_] + 1)
                nsc[to] += state_count[from_]

        if (0, c) in tr:
            to = tr[0, c]
            nml[to] = max(nml[to], 1)
            nsc[to] += 1

        max_len = nml
        state_count = nsc

        for ac in accept:
            maximum_len = max(maximum_len, max_len[ac])
            total_count += state_count[ac]

    return maximum_len, total_count


def solve(n, t):
    # 0000
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('1')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 0001
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('11*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 0010
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('1|10(0|1)*|110*1(0|1)*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 0011
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('1(0|1)*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 0100
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('1|(0|1)*01|(0|1)*10*11')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 0101
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('(0|1)*1')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 0110
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('0*1(0*10*1)*0*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 0111
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('(0|1)*1(0|1)*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 1000
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('1|00|001|010|011|100|110|(0|1)(0|1)(0|1)(0|1)(0|1)*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 1001
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('1*(01*01*)*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 1010
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('1|00|10|(0|1)(0|1)(0|1)(0|1)*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 1011
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('1(0|1)*|01*0(0|1)*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 1100
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('1|00|01|(0|1)(0|1)(0|1)(0|1)*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 1101
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('(0|1)*1|(0|1)*01*0')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 1110
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa(
        '1|00|01|10|000|001|010|011|100|110|111|(0|1)(0|1)(0|1)(0|1)(0|1)*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)

    # 1111
    dfa_states, dfa_trans, dfa_start, dfa_accepts = regex_to_dfa('1|(0|1)(0|1)(0|1)*')
    l, m = automaton(len(dfa_states), dfa_trans, dfa_accepts, t)
    print(l, m)


n = int(input())
t = input()
solve(n, t)