Overview

Given evaluation points for \(N\) employees, we need to efficiently handle two types of operations: “add \(v\) to all employees whose employee number is a multiple of \(k\)” (update operation), and “find the total sum from employee \(1\) to \(x\)” (query operation).

Since the update targets follow the regularity of “multiples,” the number of addition steps \(N/k\) varies dramatically depending on the size of \(k\). We exploit this observation and solve the problem using square root decomposition (or threshold-based processing switching).

Analysis

Naive Approach

1. Operation 1: Add \(v\) to all multiples of \(k\) (\(k, 2k, \dots\)). In the worst case (\(k=1\)), this takes \(O(N)\).
2. Operation 2: Calculate the sum from \(1\) to \(x\). Computing this naively takes \(O(N)\).

Repeating these \(Q\) times yields a worst-case complexity of \(O(NQ)\), which is too slow for the given constraints (\(N=2 \times 10^5, Q=10^5\)).

Optimization Idea

The cost of an update is large when \(k\) is small and small when \(k\) is large. Therefore, we switch the processing strategy at a certain threshold \(B\).

1. When \(k\) is small (\(k \le B\))

Instead of adding to all multiples of \(k\) each time, we record “how much total value \(v\) has been applied to each \(k\)” (count_small[k]). When operation 2 asks for the sum from \(1\) to \(x\), the contribution from this \(k\) is: $\(\text{contribution} = \sum_{k=1}^{B} (\text{count\_small}[k] \times \lfloor x/k \rfloor)\)\( Here, \)\lfloor x/k \rfloor\( represents how many multiples of \)k\( are contained in \)1\( through \)x\(. This calculation can be done in \)O(B)$.

2. When \(k\) is large (\(k > B\))

When \(k\) is large, there are at most \(N/B\) multiples of \(k\). Therefore, directly adding to the array keeps the computation manageable. However, to speed up the sum retrieval in operation 2, we combine direct addition with square root decomposition or cumulative sum management. The provided code uses a block-based approach (block decomposition) that maintains block-wise sums to speed up sum retrieval.

Algorithm

1. Initialization:
   • Precompute the prefix sum prefix_S of the initial evaluation points \(S_i\).
   • Determine the threshold \(B\) (e.g., 250).
2. Operation 1 (Update):
   • If \(k \le B\): Add \(v\) to count_small[k].
   • If \(k > B\): For each multiple \(j = k, 2k, \dots\) of \(k\), add \(v\) to the individual addition array T_large[j] for that employee and to the block sum block_sum_large for the block that employee belongs to.
3. Operation 2 (Query):
   • First, retrieve the initial prefix sum prefix_S[x].
   • Next, compute the addition from \(k > B\) using block sums and the individual additions for the partial block.
   • Finally, compute the addition from \(k \le B\) as \(\sum_{k=1}^{B} \text{count\_small}[k] \times \lfloor x/k \rfloor\), and output the total sum of all parts.

Complexity

Let \(B\) be the threshold and \(S\) be the block size. - Time Complexity: \(O(Q \times \max(B, N/B, N/S))\) - Operation 1 (\(k \le B\)): \(O(1)\) - Operation 1 (\(k > B\)): \(O(N/B)\) - Operation 2: \(O(B + N/S + S)\) - By setting \(B \approx \sqrt{N}\), the overall complexity becomes approximately \(O(Q\sqrt{N})\). - Space Complexity: \(O(N)\) - Arrays are needed to hold the prefix sums and the addition values for each employee.

Implementation Notes

• Optimization in Python: Since Python loops are slow, techniques such as using slices with built-in functions like sum(T_large[start:end]), or reading all input at once with sys.stdin.read().split(), are effective.

• Threshold Tuning: The theoretically optimal value is \(\sqrt{N}\), but adjusting to around \(B=250\) considering language characteristics and constant factor overhead optimizes the execution time.

• Block Decomposition: Using x >> S_SHIFT (bit shift) instead of division allows fast determination of which block an employee belongs to.

  Source Code

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

---

This editorial was generated by gemini-3-flash-thinking.