Ｓｋｙ株式会社プログラミングコンテスト2026（AtCoder Beginner Contest 455）F,G問題メモ

重さ $a,b$ を合成済みのスライムと、$c,d$ を合成済みのスライムのコストは $(a+b)(c+d)=ac+ad+bc+bd$ となる。

この時、$a,b$ 合成時に $ab$、$c,d$ 合成時に $cd$ のコストもかかっていて、 合わせると「初期状態のスライムの重さの、全ての2つ組の積」の総和がコストとなっている。

このように、相異なるスライムの組 $(i, j)$ に対して、その組に由来するコストは、 「それぞれが合成されたもの」を合成するタイミングで、

• $(○+○+...+B_i+...+○)(○+○+...+B_j+...+○)$

を展開した結果として $B_iB_j$ だけ寄与し、この他にコストは発生しない。

合成順に依らず、コストは $\displaystyle \sum_{i \lt j}B_iB_j$ となる。

from atcoder.lazysegtree import LazySegTree


def solve(n, q, queries):
    MOD = 998244353

    # 区間長, 総和, 1つになるまでの合成コスト
    def merge(a, b):
        return [a[0] + b[0], (a[1] + b[1]) % MOD, (a[2] + b[2] + a[1] * b[1]) % MOD]

    def mapping(a, b):
        if a == 0:
            return b
        return [b[0], (b[1] + a * b[0]) % MOD, (b[2] + (b[0] - 1) * a * b[1] + (b[0] - 1) * a * a * b[0] // 2) % MOD]

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

    init = [[1, 0, 0] for _ in range(n)]
    lst = LazySegTree(merge, [0, 0, 0], mapping, composition, 0, init)


    buf = []
    for l, r, a in queries:
        lst.apply(l - 1, r, a)
        buf.append(lst.prod(l - 1, r)[2])
    return buf


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

import random
from collections import defaultdict


def by_appear_count(n, aaa, b):
    """ 半開区間 [l, r) 内でどの値も b 個以下となる区間ごとに、良い区間の個数を求める。 """
    hash_cache = {}

    def get_hash(a, c):
        c %= b
        if a not in hash_cache:
            hash_cache[a] = []
        if len(hash_cache[a]) <= c:
            if c == b - 1:
                x = 0
                for h in hash_cache[a]:
                    x ^= h
            else:
                x = random.randrange(1, 1 << 62)
            hash_cache[a].append(x)
        return hash_cache[a][c]

    interval_count = defaultdict(int)
    r = 0  # 半開区間 [l, r) の右端

    appear_count = defaultdict(int)
    interval_hashes = defaultdict(int, {0: 1})
    hashes = [0] * (n + 1)
    result = 0

    for l in range(n):
        while r < n and interval_count[aaa[r]] + 1 <= b:
            a = aaa[r]
            interval_count[a] += 1

            if b == 1:
                result += r - l + 1
            else:
                h = hashes[r] ^ get_hash(a, appear_count[a])
                appear_count[a] += 1
                hashes[r + 1] = h
                result += interval_hashes[h]
                interval_hashes[h] += 1

            # print(f'{aaa=} {b=} {l=} {r=} {result=} {interval_count=}')
            # print(f'{aaa=} {b=} {l=} {r=} {result=} {interval_hashes=}')
            # print(f'{aaa=} {b=} {l=} {r=} {result=} {hashes=}')

            r += 1

        if r == n:
            break

        interval_count[aaa[l]] -= 1
        if b > 1:
            interval_hashes[hashes[l]] -= 1

        if r == l:
            r += 1

        # print(f'{aaa=} {b=} {l=} {r=} {result=} {interval_count=}')
        # print(f'{aaa=} {b=} {l=} {r=} {result=} {interval_hashes=}')
        # print(f'{aaa=} {b=} {l=} {r=} {result=} {hashes=}')

    return result


def by_kind_count(n, aaa, b):
    """ 区間内の種類数がちょうど b となる区間ごとに、良い区間の個数を求める。 """

    hash_cache = {}
    MOD = (1 << 44) + 7

    def get_hash(a):
        if a not in hash_cache:
            hash_cache[a] = random.randrange(1, 1 << 44)
        return hash_cache[a]

    def exact_b_kind_ranges():
        """各 l に対し、区間 [l, r] の種類数がちょうど b となる右端 r の下限・上限を求める。

        lo: 閉区間 [l, r] の種類数が b になる最小の r
        hi: 開区間 [l, r) の種類数が b になる最大の r
        → 種類数がちょうど b になる r の区間: [lo, hi)

        また同時に、その b 個の値にランダムな値を割り当て、1個ずつの総和をハッシュとして求める。
        ただし、lo[l]=hi[l] であるような l からは b 個の値が取れないので、ハッシュも意味の無い値となっている。
        """
        lo_count = defaultdict(int)
        lo_kind = 0
        p = 0
        hi_count = defaultdict(int)
        hi_kind = 0
        q = 0
        lo = []
        hi = []
        h = 0
        hhh = []

        for l in range(n):
            # p: ちょうど b 種類に到達する最小の境界まで伸ばす
            while p < n and lo_kind < b:
                a = aaa[p]
                if lo_count[a] == 0:
                    lo_kind += 1
                    h = (h + get_hash(a)) % MOD
                lo_count[a] += 1
                p += 1
            # q: b+1 種類目が入る直前まで伸ばす（種類数 <= b を保てる最大の境界）
            while q < n and (hi_count[aaa[q]] > 0 or hi_kind < b):
                a = aaa[q]
                if hi_count[a] == 0:
                    hi_kind += 1
                hi_count[a] += 1
                q += 1

            if lo_kind < b:
                lo.append(q)
                hi.append(q)
            else:
                lo.append(p - 1)
                hi.append(q)

            hhh.append(h)

            a = aaa[l]
            lo_count[a] -= 1
            if lo_count[a] == 0:
                lo_kind -= 1
                h = (h - get_hash(a)) % MOD
            hi_count[a] -= 1
            if hi_count[a] == 0:
                hi_kind -= 1

        return lo, hi, hhh

    lo, hi, hhh = exact_b_kind_ranges()
    acc = [0]
    for i in range(n):
        a = aaa[i]
        acc.append((acc[-1] + get_hash(a)) % MOD)

    interval_hashes = defaultdict(int)
    result = 0
    for l in range(n):
        if lo[l] == hi[l]:
            continue

        h = hhh[l]
        l_hash = (acc[l] * b - h * l) % MOD

        if l > 0 and hhh[l] == hhh[l - 1]:
            for i in range(lo[l - 1], lo[l]):
                tmp = (acc[i + 1] * b - h * (i + 1)) % MOD
                interval_hashes[tmp] -= 1
        else:
            interval_hashes.clear()
            for i in range(lo[l], hi[l]):
                tmp = (acc[i + 1] * b - h * (i + 1)) % MOD
                interval_hashes[tmp] += 1

        result += interval_hashes[l_hash]

    return result


def solve(n, k, aaa, bbb):
    buf = []
    for b in bbb:
        ans1 = by_appear_count(n, aaa, b)
        ans2 = by_kind_count(n, aaa, b)
        buf.append(f'{ans1} {ans2}')
    return buf


t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    aaa = list(map(int, input().split()))
    bbb = list(map(int, input().split()))
    ans = solve(n, k, aaa, bbb)
    print('\n'.join(ans))