I haven’t written an answer like this before - please criticise if it is wrong.

Let’s introduce some notation:

\quad q queries

\quad n monsters

\quad b blocks, each block of size s=q/b queries

There are four major steps in the solution:

- For each block we iterate over each query in the block. Total time O(q)
- We have to do b Sum-over-subset operations, each takes time O(n \log n)
- After each block we update the health points of each monster using a result of the Sum-over-subset operation. The update takes constant time O(1) for each monster.
- Each monster dies during some block. To find out precisely when takes time O(s).

Add the above items, and we have total time O(q + b n \log n + b n + n s).

O(bn) is smaller than O(bn \log n), so we can simplify the total time to O(q + b n \log n + n s).

Finally, we can choose to set number of blocks b to \sqrt q. So total time now O(q + \sqrt q n \log n).

Perhaps we could set b to \sqrt{\frac q {\log n}}, which would reduce the total time to O(q + n \sqrt{q \log n}).

**Updated** to include the initial iteration over each query