## G - Add and Multiply Queries Editorial by en_translator

Consider a type-\(3\) query. Let \(M\) be the maximum \(A\).

First, for \(i = l\) we have \(v = 0\), so we should always replace \(v\) with \(v + A[i]\). By the constraints, now \(v\) has become positive. An important observation is that you choose to replace \(v\) with \(v \times B[i]\) at most \(\log_2 M (< 60)\) times roughly, because \(2^{60} > 10^{18}\) and the input never allows us to perform this operation more than \(60\) times.

Therefore, the `while true:`

loop in the algorithm below iterates at most \(59\) times:

```
v = A[l]
while true:
next_l = min(r, smallest i after l + 1 such that B[i] >= 2)
v += sum_a(l + 1, next_l)
v = max(v + A[next_l], v * B[next_l])
l = next_l
if (l == r):
break
output(v)
```

By using a segment tree appropriately, the complexity becomes \(O(N + Q \log N \log M)\). The constant factor is very small, so this algorithm is fast enough.

posted:

last update: