概要

「\(k\) の倍数に一括加算」と「先頭 \(x\) 人の合計」を混在して高速に処理する問題です。\(\sqrt{N}\) を境に更新方法を切り替えることで、全クエリを現実的な時間で処理します。

考察

素朴解が間に合わない理由

操作1（1 k v）をそのまま実装すると、\(k,2k,3k,\dots\) に対して加算するため、1回の更新に \(O(N/k)\) かかります。
最悪の場合 \(k=1\) が多発すると 1回 \(O(N)\)、これが \(Q\) 回で \(O(NQ)\) となり、\(2\times 10^5 \times 10^5\) で到底間に合いません。

操作2（2 x）も、毎回 \(\sum_{i=1}^x T_i\) を愚直に足すと \(O(N)\) で同様に厳しいです。

重要な観察：小さい \(k\) と大きい \(k\) で性質が違う

• \(k\) が小さいと、倍数の個数 \(N/k\) が多いので、更新を直接やると重い。
• \(k\) が大きいと、倍数の個数 \(N/k\) が少ない（高々 \(\sqrt{N}\) 程度）ので、直接更新してもそこまで重くない。

そこで、\(B \approx \sqrt{N}\) を境に分けます。

さらに、操作2は「prefix sum（前からの累積和）」なので、点更新・区間和が得意な Fenwick Tree（BIT） を使うと高速に求められます。

アルゴリズム

方針（平方分割 + BIT）

• \(B=\lfloor \sqrt{N} \rfloor + 1\) とする。
• 大きい \(k\)（\(k>B\)）の更新は、倍数の個数が少ないので、対象 \(j=k,2k,3k,\dots\) に対して
  • BIT に 点加算（bit_add(j, v)）を行う。
• 小さい \(k\)（\(k\le B\)）の更新は、後回しにして
  • add_small[k] += v として「\(k\) の倍数に足す値」を蓄積しておく（遅延適用）。

操作2（2 x）の計算方法

求めたいのは \(\sum_{i=1}^x T_i\)。

• まず BIT から、初期値 +（大きい \(k\) の更新分）を含む prefix sum を得る：
  • res = bit_sum(x)
• 次に、小さい \(k\) の更新分はまだ BIT に入っていないので、ここでまとめて足す。

「1 k v を小さい \(k\) として遅延している」とき、\([1,x]\) の中にある \(k\) の倍数の個数は [ \left\lfloor \frac{x}{k} \right\rfloor ] なので、その寄与は [ add_small[k] \times \left\lfloor \frac{x}{k} \right\rfloor ] これを \(k=1..B\) で加算します。

具体例

例えば 1 2 10（2の倍数に+10）が遅延されていて、2 7 を聞かれたら、\([1,7]\) の 2 の倍数は \(2,4,6\) の3個なので、加算分は \(10 \times 3 = 30\) になります（\(7//2=3\)）。

計算量

• 時間計算量:

  • 操作1（更新）
    • \(k \le B\): \(O(1)\)（配列に加算するだけ）
    • \(k > B\): 対象は高々 \(N/k \le N/(B+1)=O(\sqrt{N})\) 個、各点加算が \(O(\log N)\)
      よって \(O(\sqrt{N}\log N)\)
  • 操作2（クエリ）:
    • BITのprefix sumが \(O(\log N)\)
    • 小さい \(k\) を全部見るのに \(O(B)=O(\sqrt{N})\)
      よって \(O(\sqrt{N}+\log N)\)
  • 全体として概ね \(O\big(Q(\sqrt{N}+\sqrt{N}\log N)\big)\) 程度で十分高速

• 空間計算量: \(O(N + B)\)（BIT用配列 + 遅延配列）

実装のポイント

• BIT は 1-indexed で管理します（社員番号と相性が良い）。

• 小さい \(k\) の更新は BIT に入れないで、add_small[k] に貯め、クエリ時に \(\left\lfloor x/k \right\rfloor\) 個分をまとめて足します。

• 大きい \(k\) は倍数の列挙 for j in range(k, N+1, k) が軽いので、そのまま BIT に点加算します。

• 出力は最大でも \(2^{63}-1\) に収まる保証があるため、Python の整数で安全に扱えます（ただし他言語なら 64bit 整数が必要）。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    a = [0] * (N + 1)
    for i in range(1, N + 1):
        a[i] = next(it)

    # Fenwick Tree build in O(N)
    bit = a[:]
    for i in range(1, N + 1):
        j = i + (i & -i)
        if j <= N:
            bit[j] += bit[i]

    def bit_add(i, v):
        while i <= N:
            bit[i] += v
            i += i & -i

    def bit_sum(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    B = int(N ** 0.5) + 1
    add_small = [0] * (B + 1)

    out = []
    for _ in range(Q):
        t = next(it)
        if t == 1:
            k = next(it)
            v = next(it)
            if k <= B:
                add_small[k] += v
            else:
                for j in range(k, N + 1, k):
                    bit_add(j, v)
        else:
            x = next(it)
            res = bit_sum(x)
            for k in range(1, B + 1):
                vk = add_small[k]
                if vk:
                    res += vk * (x // k)
            out.append(str(res))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。