Let \(M=\max x_i\).

If \(M\) is about \(10^5\) or all \(x_i\) is known beforehand, we can apply a coordinate compression to solve the problem with a segment tree, where each node maintains:

• the number of elements of \(A\) between \(l\) (inclusive) and \(r\) (exclusive)
• the sum of the odd-indexed elements of \(A\) between \(l\) and \(r\) when they are sorted in ascending order
• the sum of the even-indexed elements of \(A\) between \(l\) and \(r\) when they are sorted in ascending order.

However, in this problem \(M\) is large, so we cannot create a segment tree of size \(M\). In such case, we can solve it using a dynamic segment tree.

An ordinary segment tree initially constructs \(O(M)\) nodes, so it will run out of memory if \(M\) is large. However, if \(Q\ll M\), most nodes remains the identity element and not accessed, so using a dynamic segment tree is effective, where new nodes are created only when needed.

In a dynamic segment tree, each node stores not only the information on the monoid, but also pointers to (or the indices of) its parent and left/right children.

The number of nodes required is bounded by \(O(Q\log M)\), and so is the computational complexity.