トヨタ自動車プログラミングコンテスト2024#12（AtCoder Beginner Contest 384）F,G問題メモ

from collections import Counter


def solve_sub2(aaa, bbb):
    n = len(aaa)
    m = len(bbb)
    thr = 10000
    if n * m < thr:
        ans = 0
        for a, ac in aaa.items():
            for b, bc in bbb.items():
                x = a + b + 1
                while x & 1 == 0:
                    x >>= 1
                ans += x * ac * bc
        return ans
    ao, ae, bo, be = {}, {}, {}, {}
    aot, aet, bot, bet = 0, 0, 0, 0
    aoc, aec, boc, bec = 0, 0, 0, 0
    for a, ac in aaa.items():
        if a & 1:
            ao[a >> 1] = ac
            aot += a * ac
            aoc += ac
        else:
            ae[a >> 1] = ac
            aet += a * ac
            aec += ac
    for b, bc in bbb.items():
        if b & 1:
            bo[b >> 1] = bc
            bot += b * bc
            boc += bc
        else:
            be[b >> 1] = bc
            bet += b * bc
            bec += bc
    ans = aot * boc + aoc * bot + aoc * boc
    ans += aet * bec + aec * bet + aec * bec
    ans += solve_sub2(ao, be)
    ans += solve_sub2(ae, bo)
    return ans


def solve_sub1(aaa, carry):
    n = len(aaa)
    thr = 100
    # thr = 2
    if n < thr:
        ans = 0
        aaa_lst = list(aaa.keys())
        for i in range(n):
            a = aaa_lst[i]
            ac = aaa[a]
            x = a + a + carry
            while x & 1 == 0:
                x >>= 1
            ans += x * ac * (ac + 1) // 2

            for j in range(i + 1, n):
                b = aaa_lst[j]
                bc = aaa[b]
                x = a + b + carry
                while x & 1 == 0:
                    x >>= 1
                ans += x * ac * bc
        return ans

    odd = {}
    even = {}
    ot, et = 0, 0
    oc, ec = 0, 0
    for a, ac in aaa.items():
        if a & 1:
            odd[a >> 1] = ac
            ot += a * ac
            oc += ac
        else:
            even[a >> 1] = ac
            et += a * ac
            ec += ac

    if carry == 0:
        ans = ot * ec + et * oc
        ans += solve_sub1(odd, 1)
        ans += solve_sub1(even, 0)
    else:
        ans = 0
        ans += ot * (oc + 1) + oc * (oc + 1) // 2
        ans += et * (ec + 1) + ec * (ec + 1) // 2
        ans += solve_sub2(odd, even)

    return ans


def solve(n, aaa):
    aaa = Counter(aaa)
    ans = solve_sub1(aaa, 0)
    return ans


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

import os
import sys

import numpy as np


def solve(inp):
    FENWICK_TABLES = []

    def fenwick_init(n):
        table = np.zeros(n + 1, np.int64)
        FENWICK_TABLES.append(table)
        return len(FENWICK_TABLES) - 1

    def fenwick_add(ins, i, x):
        i += 1
        table = FENWICK_TABLES[ins]
        size = table.size - 1
        while i <= size:
            table[i] += x
            i += i & -i

    def fenwick_sum(ins, i):
        i += 1
        table = FENWICK_TABLES[ins]
        s = 0
        while i > 0:
            s += table[i]
            i -= i & -i
        return s

    def update(fwt, all_val, all_cnt, a, ai):
        s = fenwick_sum(fwt, ai)
        small_sum = s >> 17
        small_cnt = s & 0b1_1111_1111_1111_1111
        large_sum = all_val - small_sum
        large_cnt = all_cnt - small_cnt
        result = a * small_cnt - small_sum
        result += large_sum - a * large_cnt
        return result

    n = inp[0]
    aaa = inp[1:n + 1]
    bbb = inp[n + 1:n + n + 1]
    k = inp[n + n + 1]

    values = set(aaa) | set(bbb)
    values = sorted(values)
    to_index = {a: i for i, a in enumerate(values)}
    m = len(values)

    bucket_size = n // int(k ** 0.5) * 2
    bucket_count = (n - 1) // bucket_size + 1
    tuple_list = [(n, n, n)]
    tuple_list.clear()
    buckets = [tuple_list.copy() for _ in range(bucket_count)]
    for i in range(k):
        x = inp[n + n + 2 + i * 2]
        y = inp[n + n + 3 + i * 2]
        bi = (x - 1) // bucket_size
        buckets[bi].append((y, x, i))

    ans = np.zeros(k, np.int64)
    fwt_a = fenwick_init(m)
    all_a_sum = 0
    i = 0
    for bkt in buckets:
        fwt_b = fenwick_init(m)
        all_b_sum = 0
        j = 0
        tmp = 0

        bkt.sort()
        for y, x, qi in bkt:
            while i < x:
                a = aaa[i]
                ai = to_index[a]
                fenwick_add(fwt_a, ai, (a << 17) | 1)
                all_a_sum += a
                tmp += update(fwt_b, all_b_sum, j, a, ai)
                i += 1
            while i > x:
                a = aaa[i - 1]
                ai = to_index[a]
                fenwick_add(fwt_a, ai, -((a << 17) | 1))
                all_a_sum -= a
                tmp -= update(fwt_b, all_b_sum, j, a, ai)
                i -= 1
            while j < y:
                b = bbb[j]
                bi = to_index[b]
                fenwick_add(fwt_b, bi, (b << 17) | 1)
                all_b_sum += b
                tmp += update(fwt_a, all_a_sum, x, b, bi)
                j += 1
            ans[qi] = tmp

    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))