H - Heavy Buckets Editorial by en_translator
We adopt a trick called binary lifting. For integers \(d\) and \(i\) with \(0 \leq d < 30\) and \(1 \leq i \leq N\), define \(P_{d, i}\) and \(Q_{d, i}\) as:
- \(P_{d, i}\): when person \(i\) is holding a bucket, if the operation is performed \(2^d\) times, which person holds that bucket?
- \(Q_{d, i}\): when person \(i\) is holding a bucket, if the operation is performed \(2^d\) times, what amount of water does that bucket newly contain?
Computing \(P_{d, i}\) is merely a composition; for \(j = P_{d - 1, i}\), we have \(P_{d, i} = P_{d - 1, j}\).
Now consider \(Q_{d, i}\). Define \(j = P_{d - 1, i}\), as before. During the former \(2^{d-1}\) operations, the amount of water increases by \(Q_{d - 1, i}\). On the other hand, right before the latter \(2^{d - 1}\) operations, that bucket is held by person \(j\), so during the latter \(2^{d - 1}\) operations, the water increases by \(Q_{d - 1, j}\). Thus, \(Q_{d, i} = Q_{d - 1, i} + Q_{d - 1, j}\).
This way, the binary-lifting table can be obtained.
Based on these results, one can answer each query by performing a simulation.
For \(d = 0, 1, \ldots, 29\), if the \(2^d\)s place of \(T_i\) (in the binary representation) is \(1\), the \(2^d\) operations can be simulated using the precalculated table. It is sufficient to manage the amount of water in the bucket, and the person who holds the bucket.
The time complexity is \(O((N + Q) \log T)\), where \(T\) is the upper bound of the number of operations (in this problem, \(T = 10^9\)). It can also be solved in \(O(N + Q)\) time too.