まずはより簡単な問題を 2 つ考えます。

問題1

操作 1 において \(k\leq 100\) である。他の制約は元の問題と同じ。

解法

\(k\) の最大値(ここでは \(100\) ) を \(K\) とします。

\(0\) で初期化された配列 memo を用意し、 memo[k] で \(k\) の倍数にいくつが加算されたかを保持します。
操作 1 は memo[k] を更新するため \(O(1)\) で行えます。
操作 2 は社員 \(x\) までに社員番号が \(k\) の倍数の人は \(\lfloor\frac{x}{k}\rfloor\) 人いるため、 \(\sum_{k=1}^{K}(\mathrm{memo}[k]\times \lfloor\frac{x}{k}\rfloor)\) として \(O(K)\) で求めることができます。

問題 2

操作 1 において \(k \geq \frac{N}{100}\) である。他の制約は元の問題と同じ。

解法

\(k\) の最小値の分母に出てくる数(ここでは \(100\) ) を \(K\) とします。

操作 1 によって評価が更新される人は高々 \(K\) 人です。よって、評価ポイントをfenwick treeなどで管理することで、操作 1 は \(O(K\log N)\) 、操作 2 は \(O(\log N)\) で処理することができます。

元の問題

問題 1 は \(k\) が小さなときに有効な解法、問題 2 は \(k\) が大きなときに有効な解法でした。
元の問題は上で述べた 2 つの問題の解法を組み合わせることで解くことができます。

適当な定数 \(K\) を用意し、 \(k\leq K\) ならば問題 1 と同様の処理を、 \(k>K\) ならば問題 2 と同様の処理を行います。

これにより操作 1 は \(O(\frac{N}{K}\log N)\) 時間、操作 2 は \(O(K+\log N)\) 時間となります。よって、 \(K=O(\sqrt{N\log N})\) ととることで、操作 1,2 とも \(O(\sqrt{N\log N})\) 時間で処理することができます。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/fenwicktree>
using namespace std;

const int B = 500;

int main(){
  int n, q;
  cin >> n >> q;
  atcoder::fenwick_tree<long long>seg(n+1);
  for(int i=1; i<=n; i++){
    int s;
    cin >> s;
    seg.add(i, s);
  }
  
  vector<long long>memo(B);
  while(q--){
    int t;
    cin >> t;
    if(t == 1){
      int k, v;
      cin >> k >> v;
      if(k < B){
        memo[k] += v;
      }else{
        for(int i=k; i<=n; i+=k){
          seg.add(i, v);
        }
      }
    }else{
      int x;
      cin >> x;
      long long ans = seg.sum(0,x+1);
      for(int i=1; i<B; i++){
        ans += (x/i) * memo[i];
      }
      cout << ans << endl;
    }
  }
}

実装例 (Python)

from atcoder.fenwicktree import FenwickTree
B = 500

n, q = map(int, input().split())
seg = FenwickTree(n+1)
S = list(map(int,input().split()))

for i, s in enumerate(S, 1):
    seg.add(i, s)

memo = [0] * B
for _ in range(q):
    t, *other = map(int, input().split())
    if t == 1:
        k, v = other
        if k < B:
            memo[k] += v
        else:
            for i in range(k, n + 1, k):
                seg.add(i, v)
    else:
        x, = other
        ans = seg.sum(0, x+1)
        for i in range(1, B):
            ans += (x // i) * memo[i]
        print(ans)