estie プログラミングコンテスト2025 （AtCoder Regular Contest 210）A,B,C問題メモ

from itertools import accumulate


def solve(n, q, queries):
    ddd = [0] * n
    x_sum = 0
    for i, x in queries:
        i -= 1
        x_sum += x
        if i == n - 1:
            ddd[i] += x
            continue
        ddd[i + 1] = max(0, ddd[i + 1] - x)
        ddd[i] += x

    ans = n * (n + 1) // 2 - x_sum
    ans += sum(accumulate(ddd))
    return ans


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

$A,B$ 内の同じ値はindexの違いなどで適当にタイブレークを決めておき、全てに順序が付くとする。

「$A$ と $B$ を合わせた多重集合の小さい方から $\frac{N}{2}$ 番目の値」を $s$ とする。

仮に $x \le s$ なる $x$ が最終的な $X$ に残らないと仮定する。 $x$ が $A$ の要素なら始めから、$B$ なら自身の番になった時に必ず $S$ に入るので、 どこかのタイミングで $S$ からあふれて捨てられていないといけない。

だが、$S.top$ は、上記の素直な解き方では単調に減少し、増加することはない。
最終的な $S.top$ が $s$ なのだから、操作の過程の中で、$S.top$ は常に $s$ 以上であった。
よって、$x$ が捨てられるタイミングは発生し得ないので、矛盾する。

from operator import add, lt


class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos, total

    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)


def solve(n, m, q, aaa, bbb, queries):
    values = set(aaa)
    values.update(bbb)
    for t, i, x in queries:
        values.add(x)
    values.add(0)
    values = sorted(values)
    mapping = {a: i for i, a in enumerate(values)}

    n2 = len(values)
    fwt_count = FenwickTreeInjectable(n2, int, add)
    fwt_total = FenwickTreeInjectable(n2, int, add)
    for a in aaa:
        i = mapping[a]
        fwt_count.add(i, 1)
        fwt_total.add(i, a)
    for b in bbb:
        i = mapping[b]
        fwt_count.add(i, 1)
        fwt_total.add(i, b)

    hl = n // 2
    hr = n + m - n // 2
    buf = []
    for t, i, x in queries:
        i -= 1
        if t == 1:
            p = aaa[i]
            aaa[i] = x
        else:
            p = bbb[i]
            bbb[i] = x
        pi = mapping[p]
        xi = mapping[x]
        fwt_count.add(pi, -1)
        fwt_count.add(xi, 1)
        fwt_total.add(pi, -p)
        fwt_total.add(xi, x)

        j, acc_cnt1 = fwt_count.lower_bound(hl, lt)
        k, acc_cnt2 = fwt_count.lower_bound(hr + 1, lt)
        ans = fwt_total.sum(j - 1) + (hl - acc_cnt1) * values[j]
        ans += fwt_total.sum(n2 - 1) - fwt_total.sum(k - 1) - (hr - acc_cnt2) * values[k]
        buf.append(ans)
    return buf


n, m, 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, m, q, aaa, bbb, queries)
print('\n'.join(map(str, ans)))

def solve(n, m, aaa):
    cap = [0] * n  # i 未満のコインを全て集めると、コイン i 何枚分の支払いが可能か
    for i in range(1, n):
        cap[i] = (cap[i - 1] + aaa[i - 1]) // 10

    res = [0] * (n + 100)
    rent = 0
    for i in range(n - 1, -1, -1):
        rent *= 10
        if aaa[i] <= rent:
            rent -= aaa[i]
            continue
        aaa[i] -= rent
        d = (aaa[i] + cap[i]) // m
        res[i] += d
        rent = max(0, d * m - aaa[i])

    ans = []
    carry = 0
    for c in res:
        c += carry
        d, r = divmod(c, 10)
        ans.append(r)
        carry = d
    while len(ans) > 1 and ans[-1] == 0:
        ans.pop()
    ans.reverse()
    ans = ''.join(map(str, ans))
    return ans


t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    ans = solve(n, m, aaa)
    print(ans)