UNICORNプログラミングコンテスト2026(AtCoder Beginner Contest 477)D,E,F,G問題メモ

def solve(n, q, queries):
    tiles = [0] * n
    for op, x in queries:
        if op == '2':
            continue
        x = int(x) - 1
        tiles[x] ^= 1
    no_tiles = set(i for i in range(n) if tiles[i] == 0)
    queries.reverse()
    ans = ['X'] * n
    for op, x in queries:
        if op == '1':
            x = int(x) - 1
            if ans[x] != 'X':
                continue
            if x in no_tiles:
                no_tiles.remove(x)
            else:
                no_tiles.add(x)
        else:
            c = x
            for i in no_tiles:
                ans[i] = c
            no_tiles.clear()
    for i in range(n):
        if ans[i] == 'X':
            ans[i] = 'a'
    ans = ''.join(ans)
    return ans


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

from heapq import heappush, heappop
from itertools import accumulate


def dijkstra(links: list[list[tuple[int, int]]], s: int, t: int = -1) -> int | list[int]:
    """ シンプルな Dijkstra
    :param links: links[u] = [ u から辺が伸びる先の (v, cost) のリスト ]
    :param s: 始点
    :param t: 終点
    :return: tが指定された場合はコスト、到達不可ならINF(1<<60)。指定されていない場合は距離配列
    """
    INF = 1 << 60
    n = len(links)
    dp = [INF] * n
    dp[s] = 0
    hq = [(0, s)]
    while hq:
        cost, u = heappop(hq)
        if dp[u] < cost:
            continue
        if u == t:
            return dp[u]
        for v, c in links[u]:
            new_cost = cost + c
            if dp[v] > new_cost:
                dp[v] = new_cost
                heappush(hq, (new_cost, v))
    if t == -1:
        return dp
    return INF


def solve(n, q, aaa, bbb, queries):
    links = [[] for _ in range(n + 1)]
    for i in range(n):
        j = (i + 1) % n
        links[i].append((j, aaa[i]))
        links[j].append((i, aaa[i]))
        links[i].append((n, bbb[i]))
        links[n].append((i, bbb[i]))
    dists_to_center = dijkstra(links, n)

    acc = [0] + list(accumulate(aaa))
    loop = acc[-1]
    buf = []
    for s, t in queries:
        s -= 1
        t -= 1
        if t == n:
            buf.append(dists_to_center[s])
            continue
        ans1 = dists_to_center[s] + dists_to_center[t]
        ans2 = acc[max(s, t)] - acc[min(s, t)]
        ans3 = loop - ans2
        buf.append(min(ans1, ans2, ans3))
    return buf


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

from atcoder.lazysegtree import LazySegTree


def solve(n, m, q, blacks, queries):
    events = []
    for i in range(n):
        l, r = blacks[i]
        events.append((i, 2, l - 1, r, -1))
    for i in range(q):
        a, b, c, d = queries[i]
        events.append((a - 1, 1, c - 1, d, i))
        events.append((b - 1, 3, c - 1, d, i))
    events.sort()

    def merge(a, b):
        return (a[0] + b[0], a[1] + b[1])

    def mapping(a, b):
        return (b[0], b[1] + a * b[0])

    def composition(a, b):
        return a + b

    init = [(1, 0) for _ in range(m)]
    lst = LazySegTree(merge, (0, 0), mapping, composition, 0, init)
    ans = [0] * q
    for i, op, l, r, qi in events:
        if op == 1:
            ans[qi] -= lst.prod(l, r)[1]
        elif op == 2:
            lst.apply(l, r, 1)
        else:
            ans[qi] += lst.prod(l, r)[1]
    return ans


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

class SegTree:
    """ 非再帰セグメント木 (atcoder.segtree 互換) """

    def __init__(self, op, e, v):
        self.op = op
        self.e = e
        n = len(v)
        self.n = n
        size = 1
        while size < n:
            size <<= 1
        self.size = size
        d = [e] * (2 * size)
        d[size:size + n] = v
        for i in range(size - 1, 0, -1):
            d[i] = op(d[2 * i], d[2 * i + 1])
        self.d = d

    def set(self, p, x):
        p += self.size
        d = self.d
        op = self.op
        d[p] = x
        p >>= 1
        while p:
            d[p] = op(d[2 * p], d[2 * p + 1])
            p >>= 1

    def get(self, p):
        return self.d[p + self.size]

    def prod(self, l, r):
        """ [l, r) の演算結果 """
        sml = smr = self.e
        l += self.size
        r += self.size
        d = self.d
        op = self.op
        while l < r:
            if l & 1:
                sml = op(sml, d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = op(d[r], smr)
            l >>= 1
            r >>= 1
        return op(sml, smr)

    def all_prod(self):
        return self.d[1]


def remove_parent_edge(n, links, root=0):
    """
    親への辺が混ざった木の隣接リスト links から、親への辺を除く。

    Parameters
    ----------
    n: int
        頂点数
    links: list[list[int]]
        隣接リスト
    root:
        根

    Returns
    -------
    (children, parents): tuple[list[list[int]], list[int]]
    children: list[list[int]]
        親を除いた隣接リスト
    parents: list[int]
        親。根は -1
    """
    parents = [-2] * n
    parents[root] = -1
    q = [root]
    while q:
        u = q.pop()
        for v in links[u]:
            if parents[v] == -2:
                parents[v] = u
                q.append(v)
    children = [[v for v in links[u] if v != parents[u]] for u in range(n)]
    return children, parents


def euler_tour(n, children, s):
    """
    オイラーツアー（頂点の訪問順）

    各頂点は、初めて入るときに加え、子から戻ってくるたびに tour_order に記録される。
    （子が k 個の頂点は k+1 回現れ、全体の長さは 2n-1）

    Returns
    -------
    (tour_order, first_visited_index, depths)
    """
    tour_order = []
    first_visited_index = [0] * n
    depths = [-1] * n
    q = [s]
    depths[s] = 0
    while q:
        u = q.pop()
        if u >= 0:
            first_visited_index[u] = len(tour_order)
            tour_order.append(u)
            for v in children[u]:
                q.append(~u)
                q.append(v)
                depths[v] = depths[u] + 1
        else:
            tour_order.append(~u)
    return tour_order, first_visited_index, depths


def hilbert_index(x: int, y: int, max_bit) -> int:
    """
    (x, y) をヒルベルト曲線順のインデックスに変換する。

    returns: ヒルベルト順序の整数
    """
    index = 0
    full_bit = (1 << max_bit) - 1

    for s in range(max_bit - 1, -1, -1):
        rx = (x >> s) & 1
        ry = (y >> s) & 1
        index <<= 2
        index |= (rx * 3) ^ ry

        # 回転処理
        if ry == 0:
            if rx == 1:
                x = full_bit - x
                y = full_bit - y
            x, y = y, x

    return index


def mo_algorithm(
        queries,
        init_state,
        add_state_left,
        add_state_right,
        remove_state_left,
        remove_state_right,
        get_ans,
        max_bit: int = 20,
):
    """
    Hilbert曲線に沿った順で Mo's Algorithm を処理する。

    Args:
        queries: (Li,Ri,*) のリストで、[Li, Ri) のクエリ指定を示す（0 <= Li <= Ri）。
                 3項目以降に要素があっても良く、get_ans に渡されることで参照できる。
        init_state(): 初期状態の生成関数（state は mutable なオブジェクトを想定）
        add_state_left(state, i): [i+1, j) の state を、[i, j) にする。
        add_state_right(state, j): [i, j) の state を、[i, j+1) にする。
        remove_state_left(state, i): [i, j) の state を、[i+1, j) にする。
        remove_state_right(state, j): [i, j+1) の state を、[i, j) にする。
        get_ans(state, query): 現在の state および query（queriesの求解中の1要素）から答えを計算する。
        max_bit: クエリの値範囲 Li,Ri < 2^x を満たす x
    """

    sorted_queries = sorted(enumerate(queries), key=lambda ip: hilbert_index(ip[1][0], ip[1][1], max_bit))

    result = [0] * len(queries)
    state = init_state()
    l = r = 0
    for qi, query in sorted_queries:
        ql = query[0]
        qr = query[1]
        while r < qr:
            add_state_right(state, r)
            r += 1
        while l > ql:
            add_state_left(state, l - 1)
            l -= 1
        while r > qr:
            remove_state_right(state, r - 1)
            r -= 1
        while l < ql:
            remove_state_left(state, l)
            l += 1
        result[qi] = get_ans(state, query)

    return result


def solve(n, q, xxx, edges, queries):
    links = [[] for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].append(v)
        links[v].append(u)
    children, parents = remove_parent_edge(n, links, 0)
    tour_order, first_visited_index, depths = euler_tour(n, children, 0)
    child_order = []
    for i in range(n * 2 - 2):
        u = tour_order[i]
        v = tour_order[i + 1]
        if depths[u] < depths[v]:
            child_order.append(v)
        else:
            child_order.append(u)

    init = [(depths[v], v) for v in tour_order]
    sgt = SegTree(min, (1 << 60, 0), init)

    events = []
    for qi in range(q):
        s, t, a, b = queries[qi]
        s -= 1
        t -= 1
        fs = first_visited_index[s]
        ft = first_visited_index[t]
        if fs > ft:
            fs, ft = ft, fs
        lca = sgt.prod(fs, ft + 1)[1]
        events.append((fs, ft, a, b, xxx[lca]))

    def init_state():
        parities = [0] * n
        color_count = [0] * (n + 1)
        counter = [n] * (n + 1)
        return parities, color_count, counter

    def add_state(state, i):
        v = child_order[i]
        x = xxx[v]
        parities, color_count, counter = state
        parities[v] ^= 1
        cc = color_count[x]
        if parities[v] == 1:
            color_count[x] += 1
            counter[cc] -= 1
        else:
            color_count[x] -= 1
            counter[cc - 1] += 1

    def get_ans(state, query):
        s, t, a, b, lca_x = query
        parities, color_count, counter = state
        ans = counter[b] - counter[a - 1]
        if color_count[lca_x] == a - 1:
            ans += 1
        if color_count[lca_x] == b:
            ans -= 1
        return ans

    result = mo_algorithm(events, init_state, add_state, add_state, add_state, add_state, get_ans)
    return result


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