Multiply Query#496

Multiply Query (Editorial)

Author: Timur Degteari

Prepared by: Timur Degteari

This problem can be solved efficiently using two key observations.

  1. Monotonicity of values: Since x_i \ge 1, once a_j \ge Y after the -th update, it will remain so after all subsequent updates. Therefore, it suffices to determine, for each index , the first update after which a_j \ge Y. If we denote this update number as , then the final answer is simply b_j = q - f(j) + 1.

  2. Bounded number of significant updates: Updates with x_i = 1 do not change the array at all, so we can skip them. For updates with x_i \ge 2, each affected element at least doubles in value. Consequently, any element can be meaningfully affected by at most \log_2(Y) such updates before reaching or exceeding .

We maintain a set containing all indices for which a_j < Y. When processing an update with x_i \ge 2:

  • Iterate through all indices j \in S that lie in the range [l_i, r_i].

  • Multiply a_j by x_i.

  • If a_j \ge Y after the multiplication, record f(j) = i and remove from (since all future updates will keep a_j \ge Y).

At first glance, this approach might appear to be O(q \cdot n). However, by observation (2), each element can be visited at most \log_2(Y) times across all updates (since each visit at least doubles its value). Using a balanced data structure (such as std::set) to efficiently query elements in a range, the total complexity becomes:

[O(q (n) + n _2(Y))]

This is efficient enough given the problem constraints.