本問題のテーマは、セグメント木を用いた順序付き(多重)集合の管理です。

セグメント木の設計

本問題の設定において、 \(S\) の要素が昇順に並んだ数列 \((a _ 1, a _ 2, \ldots ,a _ {|S|})\) を考えると、クエリ 3 で求める内容を含むモノイドを次のように構築できます。

• 数列 \(A=(x _ 1,x _ 2,\ldots ,x _ k)\) に対する \(f(A)\) を、以下の \(3\) つの値の組とする。
  • 数列の長さ \(k(A)\)
  • 数列の総和 \(s(A)\)
  • \(q(A) = \sum_{i=1}^{k} i x_i\)
• 結合された数列 \(AB\) に対する \(q(AB)\) は、 \(q(AB)=q(A)+q(B)+k(A)s(B)\) と計算できる。

本問題でのセグメント木の使用方法

値 \(a\) に対応するセグメント木の末端には、\(S\) に含まれる \(a\) の個数を \(c\) として、\(a\) が \(c\) 個並んだ数列の情報を持たせます。具体的には、\((k,s,q)=(c,ca,\frac{c(c+1)}{2}a)\) とします。\(c=0\) のときは単位元 \(e=(0,0,0)\) です。要素 \(a\) の挿入、削除は、それぞれ \(c\) を \(1\) 増減させてこの値を更新することで表現できます。なお、\(s,q\) の計算は \(998244353\) を法として行います。

本問題では、多重集合 \(S\) に一度でも現れる値を列挙し、それらが値の昇順になるように、各値についてセグメント木のインデックスを割り当てておきます。実際にクエリを処理する際には、操作する値に割り当てられているインデックスに対して操作することで、常に値が昇順に並んだ数列を管理できます。

以上により、本問題を計算量 \(O((N+Q)\log (N+Q))\) で解くことができます。

解答例

• Nachia, C++