Overview

This problem requires efficiently processing update operations that add a bonus to all employees whose employee numbers are multiples of \(k\), and query operations that compute the sum of evaluation points from employee \(1\) to \(x\). We solve it using a hybrid approach combining sqrt decomposition and BIT (Fenwick Tree).

Analysis

Naive Approaches and Their Issues

First, let’s consider two naive methods.

Method A: Directly update all multiples For operation 1, add \(v\) to all multiples of \(k\), and for operation 2, retrieve the range sum using a BIT. When \(k=1\), we need to update \(N\) elements, resulting in worst-case \(O(QN \log N)\), which causes TLE.

Method B: Record updates and compute at query time For operation 1, just record the pair \((k, v)\), and for operation 2, compute the contribution of each \((k, v)\) to \(\sum_{i=1}^{x} T_i\) as \(v \times \lfloor x/k \rfloor\). However, since we scan through all accumulated operations, this results in worst-case \(O(Q^2)\), which also risks TLE.

Key Insight: Change strategy based on the size of \(k\)

When \(k\) is small: There are many multiples (\(N/k\)), so adding to the BIT one by one is costly. However, at query time we can compute the contribution as \(v \times \lfloor x/k \rfloor\) in \(O(1)\).

When \(k\) is large: There are few multiples (\(N/k\) is small), so directly adding to the BIT is fast.

Leveraging this property, we set a threshold \(B\) and handle \(k \leq B\) and \(k > B\) differently.

Algorithm

Set the threshold \(B \approx \sqrt{N \log N}\) (in the implementation, \(B = 900\)).

Operation 1 (Update: \(k, v\))

• If \(k \leq B\): Simply add \(v\) to bonus_small[k] (\(O(1)\)).
• If \(k > B\): Add \(v\) to the BIT for each multiple \(k, 2k, 3k, \ldots\) (\(O(\frac{N}{k} \log N)\), and since \(k > B\), this is at most \(O(\frac{N}{B} \log N)\)).

Operation 2 (Query: \(x\))

The answer is the sum of the following three parts:

1. Prefix sum of initial values: Precomputed cumulative sum prefix_S[x] (\(O(1)\)).
2. Contribution of small \(k\): \(\displaystyle\sum_{k=1}^{B} \text{bonus\_small}[k] \times \lfloor x/k \rfloor\) (\(O(B)\)).
3. Contribution of large \(k\): Retrieve the sum of range \([1, x]\) from the BIT (\(O(\log N)\)).

Concrete Example

With \(N=6\), when operation 1 \((k=2, v=3)\) arrives, \(3\) is added to employees \(2, 4, 6\).

• Since \(k=2 \leq B\), we do bonus_small[2] += 3.
• Then, when operation 2 \((x=5)\) arrives, the contribution from small \(k\) is computed as \(\text{bonus\_small}[2] \times \lfloor 5/2 \rfloor = 3 \times 2 = 6\) (accounting for employees 2 and 4).

Complexity

• Time complexity: \(O\!\left(Q \cdot \left(\frac{N}{B} \log N + B\right)\right)\)
  • Setting \(B = \sqrt{N \log N}\) gives \(O(Q \sqrt{N \log N})\)
  • Sufficiently fast for \(N = 2 \times 10^5\), \(Q = 10^5\)
• Space complexity: \(O(N)\) (BIT, cumulative sum array, bonus_small array)

Implementation Notes

• Choosing the threshold \(B\): \(B = \sqrt{N \log N}\) is the theoretically optimal value, but it’s best to tune it empirically considering constant factors. Here we use \(B = 900\).

• Speeding up the bonus_small loop: During queries, adding a check for bonus_small[k] != 0 allows skipping values of \(k\) that have never been updated, improving the constant factor.

• Batch output: In Python, calling print each time is slow, so we accumulate results in a list and output them all at once using sys.stdout.write at the end.

• Overflow: The problem guarantees that values fit in 64-bit integers, but since Python uses arbitrary-precision integers, this is not a concern.

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.