Overview

This problem requires efficiently processing a mix of “bulk addition to multiples of \(k\)” and “sum of first \(x\) people” queries. By switching the update method at a threshold of \(\sqrt{N}\), all queries can be processed in a practical amount of time.

Analysis

Why the naive solution is too slow

If we implement Operation 1 (1 k v) directly, we add to \(k, 2k, 3k, \dots\), so a single update costs \(O(N/k)\).
In the worst case, if \(k=1\) occurs frequently, each update is \(O(N)\), and with \(Q\) such updates we get \(O(NQ)\), which is \(2\times 10^5 \times 10^5\) — far too slow.

Operation 2 (2 x) is similarly expensive if we naively compute \(\sum_{i=1}^x T_i\) in \(O(N)\) each time.

Key observation: small \(k\) and large \(k\) behave differently

• When \(k\) is small, the number of multiples \(N/k\) is large, so direct updates are expensive.
• When \(k\) is large, the number of multiples \(N/k\) is small (at most around \(\sqrt{N}\)), so direct updates are not too costly.

Therefore, we split at a threshold \(B \approx \sqrt{N}\).

Furthermore, since Operation 2 computes a “prefix sum (cumulative sum from the beginning),” we can use a Fenwick Tree (BIT), which efficiently handles point updates and range sum queries.

Algorithm

Approach (Square Root Decomposition + BIT)

• Set \(B=\lfloor \sqrt{N} \rfloor + 1\).
• Updates with large \(k\) (\(k > B\)): Since the number of multiples is small, for each target \(j = k, 2k, 3k, \dots\):
  • Perform a point addition on the BIT (bit_add(j, v)).
• Updates with small \(k\) (\(k \le B\)): Defer them by:
  • Setting add_small[k] += v to accumulate “the value to add to multiples of \(k\)” (lazy application).

Computing Operation 2 (2 x)

We want to compute \(\sum_{i=1}^x T_i\).

• First, obtain the prefix sum from the BIT, which includes the initial values and updates from large \(k\):
  • res = bit_sum(x)
• Next, add the contributions from small \(k\) updates, which are not yet in the BIT.

When 1 k v has been deferred as a small \(k\) update, the number of multiples of \(k\) in \([1, x]\) is [ \left\lfloor \frac{x}{k} \right\rfloor ] so its contribution is [ add_small[k] \times \left\lfloor \frac{x}{k} \right\rfloor ] We sum this for \(k = 1..B\).

Concrete example

For instance, if 1 2 10 (add +10 to multiples of 2) has been deferred, and we are asked 2 7, the multiples of 2 in \([1, 7]\) are \(2, 4, 6\) — that’s 3 values — so the added contribution is \(10 \times 3 = 30\) (since \(7 // 2 = 3\)).

Complexity

• Time complexity:

  • Operation 1 (update):
    • \(k \le B\): \(O(1)\) (just adding to an array)
    • \(k > B\): There are at most \(N/k \le N/(B+1) = O(\sqrt{N})\) targets, and each point addition costs \(O(\log N)\)
      Thus \(O(\sqrt{N}\log N)\)
  • Operation 2 (query):
    • BIT prefix sum is \(O(\log N)\)
    • Iterating over all small \(k\) costs \(O(B) = O(\sqrt{N})\)
      Thus \(O(\sqrt{N} + \log N)\)
  • Overall, approximately \(O\big(Q(\sqrt{N} + \sqrt{N}\log N)\big)\), which is sufficiently fast.

• Space complexity: \(O(N + B)\) (BIT array + lazy array)

Implementation Notes

• The BIT is managed as 1-indexed (which aligns well with employee numbers).

• Small \(k\) updates are NOT added to the BIT; instead, they are accumulated in add_small[k], and at query time, the contribution of \(\left\lfloor x/k \right\rfloor\) multiples is added all at once.

• For large \(k\), enumerating multiples via for j in range(k, N+1, k) is lightweight, so we directly perform point additions on the BIT.

• The output is guaranteed to fit within \(2^{63}-1\), so it can be safely handled with Python’s integers (though other languages would require 64-bit integers).

  Source Code

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

---

This editorial was generated by gpt-5.2-high.