概要

社員番号が \(k\) の倍数である全社員にボーナスを加算する更新操作と、社員 \(1\) から \(x\) までの評価ポイントの合計を求めるクエリ操作を効率的に処理する問題です。平方分割（sqrt decomposition） と BIT（Fenwick Tree） を組み合わせたハイブリッド手法で解きます。

考察

素朴なアプローチとその問題点

まず、2つの素朴な方法を考えてみましょう。

方法A：愚直に倍数を更新 操作1で \(k\) の倍数すべてに \(v\) を加算し、操作2ではBITで区間和を取得する方法です。\(k=1\) のとき \(N\) 個の要素を更新する必要があり、最悪 \(O(QN \log N)\) となりTLEします。

方法B：更新を記録しておき、クエリ時に計算 操作1では \((k, v)\) のペアを記録するだけにし、操作2で「\(\sum_{i=1}^{x} T_i\) に対する \((k, v)\) の寄与は \(v \times \lfloor x/k \rfloor\)」と計算する方法です。しかし蓄積された操作すべてを走査するため、最悪 \(O(Q^2)\) となりこれもTLEの恐れがあります。

重要な気づき：\(k\) の大小で戦略を変える

\(k\) が小さいとき：倍数が多い（\(N/k\) 個）ので、BITに1つずつ加算するとコストが大きい。しかしクエリ時に寄与を \(v \times \lfloor x/k \rfloor\) で \(O(1)\) 計算できる。

\(k\) が大きいとき：倍数が少ない（\(N/k\) 個が小さい）ので、BITに直接加算しても高速。

この性質を利用して、閾値 \(B\) を設け、\(k \leq B\) と \(k > B\) で処理を分けます。

アルゴリズム

閾値 \(B \approx \sqrt{N \log N}\) を設定します（実装では \(B = 900\)）。

操作1（更新：\(k, v\)）

• \(k \leq B\) の場合：配列 bonus_small[k] に \(v\) を加算するだけ（\(O(1)\)）。
• \(k > B\) の場合：\(k, 2k, 3k, \ldots\) の各倍数についてBITに \(v\) を加算（\(O(\frac{N}{k} \log N)\)、\(k > B\) なので高々 \(O(\frac{N}{B} \log N)\)）。

操作2（クエリ：\(x\)）

答えは以下の3つの和です：

1. 初期値の区間和：事前に計算した累積和 prefix_S[x]（\(O(1)\)）。
2. 小さい \(k\) の寄与：\(\displaystyle\sum_{k=1}^{B} \text{bonus\_small}[k] \times \lfloor x/k \rfloor\)（\(O(B)\)）。
3. 大きい \(k\) の寄与：BITで区間 \([1, x]\) の合計を取得（\(O(\log N)\)）。

具体例

\(N=6\) で操作1 \((k=2, v=3)\) が来たとき、社員 \(2, 4, 6\) に \(3\) が加算されます。

• \(k=2 \leq B\) なので bonus_small[2] += 3。
• その後、操作2 \((x=5)\) が来ると、小さい \(k\) の寄与として \(\text{bonus\_small}[2] \times \lfloor 5/2 \rfloor = 3 \times 2 = 6\)（社員2, 4の分）が計算されます。

計算量

• 時間計算量: \(O\!\left(Q \cdot \left(\frac{N}{B} \log N + B\right)\right)\)
  • \(B = \sqrt{N \log N}\) と設定すると \(O(Q \sqrt{N \log N})\)
  • \(N = 2 \times 10^5\), \(Q = 10^5\) で十分高速
• 空間計算量: \(O(N)\)（BIT、累積和配列、bonus_small配列）

実装のポイント

• 閾値 \(B\) の選び方: \(B = \sqrt{N \log N}\) が理論的な最適値ですが、定数倍を考慮して実測で調整するのが良いです。今回は \(B = 900\) としています。

• bonus_small のループ高速化: クエリ時に bonus_small[k] != 0 のチェックを入れることで、一度も更新されていない \(k\) をスキップし定数倍を改善しています。

• 出力の一括書き出し: Python では print を毎回呼ぶと遅いため、結果をリストに溜めて最後に sys.stdout.write で一括出力しています。

• オーバーフロー: 問題文で64ビット整数に収まることが保証されていますが、Python は多倍長整数なので気にする必要はありません。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = list(map(int, input().split()))
    
    # Prefix sum of initial values
    prefix_S = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix_S[i] = prefix_S[i - 1] + S[i - 1]
    
    # BIT (Fenwick Tree) for prefix sums of the bonus additions
    # We need to support: add v to all multiples of k (up to N), query sum(1..x)
    # 
    # When we do operation 1 (k, v): for each multiple j = k, 2k, ..., add v to position j
    # When we do operation 2 (x): query sum of positions 1..x
    #
    # With N, Q <= 5*10^4, operation 1 costs O(N/k) per update which sums to O(N log N) 
    # in the worst case per query, but with Q operations it could be up to 5*10^4 * 5*10^4 = 2.5*10^9
    # in the worst case (k=1 every time).
    #
    # Let's use a BIT for point updates and prefix queries.
    # For operation 1: iterate over multiples of k and do point update on BIT. O((N/k) * log N)
    # For operation 2: prefix query on BIT. O(log N)
    #
    # Worst case: k=1 means N updates on BIT = 5*10^4 * log(5*10^4) ≈ 5*10^4 * 16 = 8*10^5 per query
    # With Q = 5*10^4 queries all with k=1: 5*10^4 * 8*10^5 = 4*10^10, too slow.
    #
    # Alternative: store bonus as (k, v) pairs and at query time compute contribution.
    # For query sum(1..x): contribution of (k, v) is v * floor(x/k) 
    # This is O(1) per stored operation per query.
    # With Q operations and Q queries: O(Q^2) = 2.5 * 10^9, borderline.
    #
    # Hybrid approach with sqrt decomposition:
    # Threshold B. For k <= B: maintain an array bonus_small[k] accumulating total v for each k.
    #   Query: sum over k=1..B of bonus_small[k] * floor(x/k). Cost O(B).
    # For k > B: use BIT point updates (each update touches N/k < N/B points).
    #   Query: BIT prefix query. Cost O(log N).
    # Update cost for k > B: O((N/k) * log N) <= O((N/B) * log N).
    # Total update cost: Q * (N/B) * log N for large k updates.
    # Total query cost for small k part: Q * B.
    # Balance: Q * N * log(N) / B = Q * B => B = sqrt(N * log N) ≈ sqrt(5*10^4 * 16) ≈ 900
    
    B = 900
    
    # For small k (k <= B)
    bonus_small = [0] * (B + 1)  # bonus_small[k] = accumulated v for this k
    
    # BIT for large k
    bit = [0] * (N + 2)
    
    def bit_update(i, val):
        while i <= N:
            bit[i] += val
            i += i & (-i)
    
    def bit_query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    out = []
    for _ in range(Q):
        line = input().split()
        if line[0] == '1':
            k = int(line[1])
            v = int(line[2])
            if k <= B:
                bonus_small[k] += v
            else:
                # Update BIT at all multiples of k
                j = k
                while j <= N:
                    bit_update(j, v)
                    j += k
        else:
            x = int(line[1])
            # Start with prefix sum of initial values
            total = prefix_S[x]
            # Add contribution from small k
            for k in range(1, B + 1):
                if bonus_small[k] != 0:
                    total += bonus_small[k] * (x // k)
            # Add contribution from large k via BIT
            total += bit_query(x)
            out.append(total)
    
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。