概要

\(N\) 人の社員の評価ポイントに対して、「社員番号が \(k\) の倍数の人に \(v\) 加算する」という更新操作と、「社員 \(1\) から \(x\) までの合計値を求める」という取得操作を効率的に行う問題です。

更新対象が「倍数」という規則性を持っているため、加算のステップ数 \(N/k\) が \(k\) の大きさによって劇的に変わる点に着目し、平方分割（または閾値による処理の切り替え）を用いて解きます。

考察

素朴なアプローチ

1. 操作 1: \(k\) の倍数すべて（\(k, 2k, \dots\)）に \(v\) を加算する。最悪の場合（\(k=1\)）は \(O(N)\) かかります。
2. 操作 2: \(1\) から \(x\) までの合計を計算する。愚直に計算すると \(O(N)\) かかります。

これらを \(Q\) 回繰り返すと、最悪計算量は \(O(NQ)\) となり、今回の制約（\(N=2 \times 10^5, Q=10^5\)）では間に合いません。

効率化のアイデア

更新のコストは \(k\) が小さいほど大きく、 \(k\) が大きいほど小さくなります。そこで、ある閾値 \(B\) を境に処理を切り替えます。

1. \(k\) が小さい場合（\(k \le B\)）

\(k\) の倍数に毎回加算する代わりに、「どの \(k\) に合計でどれだけの値 \(v\) が操作されたか」を記録しておきます（count_small[k]）。 操作 2 で \(1\) から \(x\) までの合計を求める際、この \(k\) による貢献分は以下のようになります。 $\(\text{貢献分} = \sum_{k=1}^{B} (\text{count\_small}[k] \times \lfloor x/k \rfloor)\)\( ここで \)\lfloor x/k \rfloor\( は、 \)1\( から \)x\( の中に \)k\( の倍数がいくつ含まれるかを表します。この計算は \)O(B)$ で行えます。

2. \(k\) が大きい場合（\(k > B\)）

\(k\) が大きいとき、 \(k\) の倍数は \(N/B\) 個以下しかありません。そのため、直接配列に加算しても計算量は抑えられます。 ただし、操作 2 の合計取得を高速化するために、直接加算するだけでなく、平方分割や累積和の管理を併用します。提供されたコードでは、ブロックごとの合計値を保持する手法（ブロック分解）を用いて、合計取得を高速化しています。

アルゴリズム

1. 初期化:
   • 初期評価ポイント \(S_i\) の累積和 prefix_S を計算しておきます。
   • 閾値 \(B\) （例：250）を決めます。
2. 操作 1（更新）:
   • \(k \le B\) の場合：count_small[k] に \(v\) を加算します。
   • \(k > B\) の場合：\(k\) の倍数 \(j = k, 2k, \dots\) に対して、その社員の個別加算分 T_large[j] と、その社員が属するブロックの合計 block_sum_large に \(v\) を加算します。
3. 操作 2（取得）:
   • まず、初期状態の累積和 prefix_S[x] を取得します。
   • 次に、\(k > B\) による加算分を、ブロック合計と端数の個別加算分から計算します。
   • 最後に、\(k \le B\) による加算分を \(\sum_{k=1}^{B} \text{count\_small}[k] \times \lfloor x/k \rfloor\) によって計算し、すべてを合計して出力します。

計算量

\(B\) を閾値、 \(S\) をブロックサイズとします。 - 時間計算量: \(O(Q \times \max(B, N/B, N/S))\) - 操作 1 (\(k \le B\)): \(O(1)\) - 操作 1 (\(k > B\)): \(O(N/B)\) - 操作 2: \(O(B + N/S + S)\) - \(B \approx \sqrt{N}\) と設定することで、全体で \(O(Q\sqrt{N})\) 程度になります。 - 空間計算量: \(O(N)\) - 累積和配列や各社員の加算分を保持する配列が必要です。

実装のポイント

• Pythonでの高速化: Pythonはループが遅いため、sum(T_large[start:end]) のようにスライスと組み込み関数を使ったり、sys.stdin.read().split() で入力を一括取得したりする工夫が有効です。

• 閾値の調整: 理論上の最適値は \(\sqrt{N}\) ですが、言語の特性や定数倍の重さを考慮して \(B=250\) 前後に調整することで実行時間を最適化しています。

• ブロック分解: x >> S_SHIFT （ビットシフト）を用いることで、除算を高速に行い、社員がどのブロックに属するかを素早く判定しています。”`

  ソースコード

import sys

# threshold for small k and block size for large k updates
B = 250
S_SHIFT = 8
S = 1 << S_SHIFT

def solve():
    # Fast I/O: read all input at once and split into strings
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # Precompute prefix sums of initial evaluation points S_i
    # S_list contains S_1, S_2, ..., S_N
    S_list = list(map(int, input_data[2:2+N]))
    prefix_S = [0] * (N + 1)
    curr_sum = 0
    for i in range(N):
        curr_sum += S_list[i]
        prefix_S[i+1] = curr_sum
        
    # Large k (> B) tracking:
    # T_large[i] stores the sum of bonuses added directly to employee i
    # block_sum_large[b] stores the sum of T_large within block b
    T_large = [0] * (N + 1)
    block_sum_large = [0] * ((N >> S_SHIFT) + 1)
    
    # Small k (<= B) tracking:
    # count_small[k] stores the total bonus value v added for a given multiple k
    count_small = [0] * (B + 1)
    active_small = []
    is_active_small = [False] * (B + 1)
    
    results = []
    curr = 2 + N
    # Process each query
    for _ in range(Q):
        q_type = input_data[curr]
        if q_type == '1':
            k = int(input_data[curr+1])
            v = int(input_data[curr+2])
            curr += 3
            if k > B:
                # Update all multiples of k using block decomposition
                # Optimization: use local variables for slightly faster list access
                local_T_large = T_large
                local_block_sum_large = block_sum_large
                for j in range(k, N + 1, k):
                    local_T_large[j] += v
                    local_block_sum_large[(j - 1) >> S_SHIFT] += v
            else:
                # For small k, store the bonus to calculate contribution during Query 2
                if not is_active_small[k]:
                    is_active_small[k] = True
                    active_small.append(k)
                count_small[k] += v
        else:
            x = int(input_data[curr+1])
            curr += 2
            
            # Start with the prefix sum of initial evaluation points
            res = prefix_S[x]
            
            # Add contribution from large k updates (calculated via block decomposition)
            num_full_blocks = x >> S_SHIFT
            if num_full_blocks:
                res += sum(block_sum_large[:num_full_blocks])
            
            # Sum the remaining elements of the large k updates that don't form a full block
            start_idx = (num_full_blocks << S_SHIFT) + 1
            if start_idx <= x:
                res += sum(T_large[start_idx : x + 1])
            
            # Add contribution from small k updates
            # Each update (k, v) adds v * floor(x/k) to the sum from 1 to x
            local_count_small = count_small
            for k in active_small:
                res += local_count_small[k] * (x // k)
            
            results.append(str(res))
    
    # Efficiently output all stored results for Query 2
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。