\(M=\max x_i\) とします．

もし \(M\) が \(10^5\) 程度である場合や，あらかじめすべての \(x_i\) が分かっている場合は座標圧縮することで，この問題をセグメント木で解くことができます．このとき，各ノードには以下の情報を持たせます：

• \(l\) 以上 \(r\) 未満の \(A\) の要素の個数
• \(l\) 以上 \(r\) 未満の \(A\) の要素を昇順に並べたときの，奇数番目の要素の総和
• \(l\) 以上 \(r\) 未満の \(A\) の要素を昇順に並べたときの，偶数番目の要素の総和

しかし，本問題は \(M\) が大きいためサイズが \(M\) のセグメント木を作ることができません．このような場合は 動的セグメント木 (Dynamic Segment Tree) を利用することで解くことができます．

通常のセグメント木は最初に \(O(M)\) 個のノードを構築するため \(M\) が大きいとメモリが不足します．一方で \(Q\ll M\) の場合，多くのノードは単位元のままアクセスされないため，「必要になったときに新しくノードを作る」動的セグメント木を用いることが有効です．

動的セグメント木では各ノードに，モノイドの情報に加えてbinary trie のように親ノードや左右の子ノードへのポインタ（またはインデックス）を持たせます．

必要なノード数は \(O(Q\log M)\) に抑えられ，計算量も \(O(Q\log M)\) で解くことができます．