数列の転倒数の情報を含み、かつ高速に計算できるモノイドがあれば、セグメント木を使って問題を解くことができます。

以下では、本問題においてモノイドを設計する際の手順の一例を示します。

モノイドの設計手順の例

数列 \(X\) に対してモノイドの元 \(f(X)\) を対応させるとき、数列 \(X\) , \(Y\) の連結を \(XY\) とすると、 \(f(X)\) と \(f(Y)\) から \(f(XY)\) が求まらなければなりません。しかし、 \(XY\) の転倒数は、 \(X\) の転倒数と \(Y\) の転倒数のみからは求まりません。

そのため、 \(XY\) の転倒数を求めるのに必要な情報を追加します。

転倒数の定義通りの計算では、数列内の要素 \(2\) つの組のうち条件を満たすものを数えています。 \(XY\) の転倒数で数えられる組のうち、

• 組の両方が \(X\) に含まれるものの個数と、
• 組の両方が \(Y\) に含まれるものの個数

はそれぞれ \(X\) , \(Y\) の転倒数そのものです。残りは

• 組の片方（これを \(a\) とする）が \(X\) に含まれ、もう一方（これを \(b\) とする）が \(Y\) に含まれるものの個数

が求まればよいです。数列の要素が \(0,1,2\) のみであるため、このような組が転倒数に数えられる条件は、 \((a,b)\) が \((1,0),(2,0),(2,1)\) のいずれかに等しいことです。

\((a,b)=(1,0)\) に注目すると、条件を満たす組の個数は \(X\) に含まれる \(1\) の個数と \(Y\) に含まれる \(0\) の個数の積に等しいです。ほかの \((a,b)\) についても同様です。よって、\(f(X)\) に \(X\) に含まれる \(0,1,2\) それぞれの個数の情報を含めることで、\(f(X)\) と \(f(Y)\) の情報から \(XY\) の転倒数が求まるようになります。

\(XY\) に含まれる値 \(a\) (\(a=0,1,2\)) の個数は、 \(X,Y\) それぞれに含まれる \(a\) の個数の和です。

以上より、 \(f(X)\) を以下の \(4\) つの整数の組とすることで、 \(f(XY)\) が \(f(X),f(Y)\) のみから求まるようになります。

• \(X\) の転倒数
• \(X\) に含まれる \(0\) の個数
• \(X\) に含まれる \(1\) の個数
• \(X\) に含まれる \(2\) の個数

この \(f(X)\) は空列を含め、\(0,1,2\) からなる任意の数列 \(X\) に対して定義できています。

\(f(X),f(Y)\) が与えられた場合の \(f(XY)\) の計算、および長さ \(1\) の数列 \(X\) に対する \(f(X)\) の計算は、それぞれ計算量 \(O(1)\) で実現できます。よって、セグメント木を適切に利用することで、問題を計算量 \(O(N+Q\log N)\) で解くことができます。

他の視点

ここで得られたモノイドは、AtCoder Algorithm Lectures “区間クエリのためのモノイド設計”の例題「ABC 部分列の個数」の類似としてとらえることによって得ることもできます。具体的には、本問題における転倒数は、\(3\) 種類の部分列 \((1,0),(2,0),(2,1)\) の個数の合計です。

解答例

• Nachia, C++