Let's start by considering how to evaluate the answer to a given query ~i~ at all, before worrying about how to do so efficiently. Let ~h~ be the height of the ~X_i~-th tallest skyscraper. Next, let ~c~ be the total number of height-~h~ skyscrapers, and let ~v~ be the number of height-~h~ skyscrapers which will be vaporized. Note that this means that, for any given height-~h~ skyscraper, the probability that it'll be vaporized is ~v/c~. The answer can then be expressed as the sum of the following ~3~ values:

1. The total number of citizens in the interval ~[L_i, R_i]~.
2. The expected number of citizens in vaporized height-~h~ skyscrapers outside the interval ~[L_i, R_i]~. Note that this is equal to ~v/c~ multiplied by the total number of citizens in height-~h~ skyscrapers outside the interval ~[L_i, R_i]~, due to linearity of expectation.
3. The total number of citizens in skyscrapers taller than ~h~ outside the interval ~[L_i, R_i]~.

Naively, at least values 2 and 3 take ~\mathcal O(N)~ time to compute per query, so next we'll need to look for an efficient way to share computations between queries. These two values depend on ~h~, which depends on ~X_i~, which suggests that processing the ~M~ queries in non-decreasing order of ~X~ may be most convenient. So, we'll want to input all of them, sort them by ~X~, compute and store their answers, and output them in the original order at the end.

Let's imagine that ~X~ starts off at ~0~. Then, each time ~X~ increases by one, either ~h~ decreases to a new smaller value (at which point we can count its corresponding value of ~c~, and set ~v~ to ~1~), or ~h~ stays constant and ~v~ increases by one. This means that we can easily keep track of the ~v/c~ portion of the answer. The tricky remaining part is being able to look up interval sums of ~C_i~ values efficiently, for three types of skyscrapers – all of them, only ones with exactly the current height ~h~, and only ones taller than height ~h~. An advanced data structure such as a binary indexed tree (or a more general segment tree) will do the trick here. For example, we can maintain three binary indexed trees, one for each of the three types of skyscrapers mentioned above, and update them appropriately whenever ~h~ decreases. In total, each ~C_i~ value will be inserted and removed at most once into each of the binary indexed trees, with a time complexity of ~\mathcal O(\log N)~ each, and each binary indexed tree will be queried once per query, also with a time complexity of ~\mathcal O(\log N)~ each. Overall, this approach can achieve a time complexity of ~\mathcal O((N+M) \log N)~.