\(a_i\) は降順にソートし, クエリも先読みして \(x\) の降順にソートしておく.

要素の値と個数を管理するセグメントツリーを用意する. クエリの実行の前に \(a_i \geq x\) となる \(a_i\) を値のセグメントツリーに入れ, 個数のセグメントツリーも更新する. そして, 値の方の和から \(x\) に個数を掛けたものを引き, 出力する.