類題として ARC 074 B があります。

さて、これらの問題では値を求めたい区間の形が決まっていますが、発展的なクエリ問題として以下のようなものを考えます。

長さ \(n\) の整数列 \(a = (a_0, \dots, a_{n-1})\) と \(q\) 個のクエリ \(([l_i, r_i), k_i)\) が与えられます。各クエリに対して、\((a_{l_i}, \dots, a_{r_i-1})\) を昇順に並べたときの先頭 \(k\) 個の和を答えてください。

\(\gdef\angled#1{\langle#1\rangle}\) これは、\(\langle O(n\log(n)), O(\log(n))\rangle\) や \(\angled{O(n\log(\max a)), O(\log(\max a)}\) で解くことができます（\(\angled{f(n), g(n)}\) は前処理 \(f(n)\) 時間、クエリあたり \(g(n)\) 時間を意味します）。

wavelet matrix の \(k\)-最小値クエリに似た処理を行えばよいです。本来の wavelet matrix に加えて、wavelet matrix の段数分の累積和を同時に管理することで実現可能です。

関連しそうな解説

wavelet matrix のクエリは「点 \((i, a_i)\) (\(0\le i<n\)) が与えられる。\(L\le i<R\) かつ \(D\le a_i<U\) を満たす点の個数は？」「\(L\le i<R\) を満たす点のうち下から \(k\) 個目の y 座標は？」などの形式に言い換えられますが、前述のデータ構造のクエリは「点 \((i, a_i)\) (\(0\le i<n\)) が与えられる。各点には重み \(w_i\) がついている。\(L\le i < R\) かつ \(D\le a_i<U\) を満たす点の重みの総和は？」「\(L\le i<R\) を満たす点のうち下から \(k\) 個の重みの総和は？」などの形式に言い換えられます。

この \(a_i\) を wavelet matrix で管理し、重み \(w_i\)（を適切に並べ替えたもの）の累積和を別途管理します。 \(a_i\) は整数ですが、\(w_i\) は整数ではなくてもよいです。

適切に並べ替える必要があるので、モノイドの性質を持つだけでは無理ですが、可換群（累積和ではなく disjoint sparse table などを使うと逆元を仮定しなくてよくなるので、可換モノイド）であれば扱えます。