以下のように関数を定義しておきます。

• \(count(l,r,a,b) =「l \le i \le r\) かつ \((A_i,B_i)=(a,b)\) を満たす \(i\) の個数」
• \(reverse(l,r,a,b,c,d) =「l \le i < j \le r\) かつ \((A_i,B_i)=(a,b),(A_j,B_j)=(c,d)\) を満たす \((i,j)\) の個数」

議論を楽にするため、必要ならば \((A_i,B_i)\) の先頭に \((1,2),(1,3)\) を、末尾に \((2,3)\) を挿入することで \((A_i,B_i)=(1,2),(1,3),(2,3)\) を満たす \(i\) の存在性を確保しておきます。

最適解は、\((A_i,B_i)=(1,2)\) を満たす \(i\) のうち、\(i \le x\) を満たすものについては \(C_i=1\)、\(i > x\) を満たすものについては \(C_i = 2\) という形になっています。(同様に、\((1,3),(2,3)\) についてもある \(y,z\) が存在してそのような形になっています。)

後々のため、\(x\) として取ることが出来る値は \((A_i,B_i)=(1,2)\) を満たす \(i\) もしくは \((A_i,B_i)=(1,2)\) を満たす最小の \(i\) に対する \(i-1\) のみとします。このようにしても一般性を失いません。\(y,z\) に対しても同様とします。

ここで、\(x,y,z\) を固定したときの \(A_i=B_i\) を満たす \(i\) との転倒数をそれぞれ \(P_x,Q_y,R_z\) とします。

さて、\(x,y,z\) の大小関係を固定しましょう。例えば、\(x < y < z\) のケースを考えます。このときの転倒数は以下の値の総和です。

• $P_x + Q_y + R_z$
• $x < i < j \le y$ かつ $(A_i,B_i)=(1,2),(A_j,B_j)=(1,3)$ を満たす $(i,j)$ の個数($=reverse(x+1,y,1,2,1,3)$)
• $y < i < j$ かつ $(A_i,B_i)=(1,3),(A_j,B_j)=(1,2)$ を満たす $(i,j)$ の個数($=reverse(y+1,n,1,3,1,2)$)
• $i < j \le x$ かつ $(A_i,B_i)=(2,3),(A_j,B_j)=(1,2)$ を満たす $(i,j)$ の個数($=reverse(1,x,2,3,1,2)$)
• $z < i < j$ かつ $(A_i,B_i)=(2,3),(A_j,B_j)=(1,2)$ を満たす $(i,j)$ の個数($=reverse(z+1,n,2,3,1,2)$)
• $i < j \le y$ かつ $(A_i,B_i)=(2,3),(A_j,B_j)=(1,3)$ を満たす $(i,j)$ の個数($=reverse(1,y,2,3,1,3)$)
• $y < i < j \le z$ かつ $(A_i,B_i)=(1,3),(A_j,B_j)=(2,3)$ を満たす $(i,j)$ の個数($=reverse(y+1,z,1,3,2,3)$)

よく見ると、\(x,z\) が互いに関わるような項がありません。そのため、\(y\) を固定したときの \(x\) についての値の最小値、\(z\) についての値の最小値をそれぞれ求めればよいです。

さて、\(y\) を固定したときの最小値を取る \(x\) について考えます。考えるべき項は上記のうち、\(P_x\) と \(reverse(x+1,y,1,2,1,3),reverse(1,x,2,3,1,2)\) のみです。このうち、後者は \(x\) を決めると自動的に定まりますが、前者の項が \(x,y\) に両方よって決まるため難しいです。ここで、以下のように \(reverse(x+1,y,1,2,1,3)\) を分解します。

\(reverse(x+1,y,1,2,1,3)=reverse(1,y,1,2,1,3)-reverse(1,x,1,2,1,3)-count(1,x,1,2) \times count(x+1,y,1,3)\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =reverse(1,y,1,2,1,3)-reverse(1,x,1,2,1,3)+count(1,x,1,2) \times count(1,x,1,3) - count(1,x,1,2) \times count(1,y,1,3)\)

さて、このように分解することで \(reverse(x+1,y,1,2,1,3) = f(x) + g(y) + p(x)q(y)\) の形にすることが出来ました。よって、Convex Hull Trick を使うことで各 \(y\) ごとに \(x\) 側の最小値を求めることが出来ます。そして、同様に処理することで \(z\) 側も処理することが出来ます。

これで \(x < y < z\) のケースを処理することが出来ました。そして、\(y < z < x,z < x < y\) のケースも同様に処理することが出来ます。

\(x < z < y\) のケースは上記のケースと少し挙動が異なります。先ほどと同様に転倒数をいくつかの項の和に分解します。

• $P_x + Q_y + R_z$
• $reverse(1,x,2,3,1,2)$
• $reverse(z+1,n,2,3,1,2)$
• $reverse(1,y,2,3,1,3)$
• $reverse(x+1,y,1,2,1,3)=reverse(1,y,1,2,1,3)-reverse(1,x,1,2,1,3)+count(1,x,1,2)\times count(1,x,1,3) - count(1,x,1,2) \times count(1,y,1,3)$
• $reverse(y+1,n,1,3,1,2)$

ここで、\(x,y\) を決め打ったとしましょう。すると、\(R_z + reverse(z+1,n,2,3,1,2)\) が凸であることより最適な \(z\) は \(x\) 以上の最少の \(z\)、\(y\) 以下の最大の \(z\)、全体で \(R_z + reverse(z+1,n,2,3,1,2)\) が最小値を取る \(z\) のいずれかであることが分かります。いずれの場合も Convex Hull Trick を使うことで高速に処理することが出来ます。

\(y < x < z,z < y < x\) のケースも同様に処理出来ます。よって、これにて全てのパターンを処理することが出来ました。

計算量は \(\mathrm{O}(N)\) や \(\mathrm{O}(N\log N)\) です。(\(x < z < y\) パターンで分割統治 + CHT に log をつける \(\mathrm{O}(N\log^2 N)\) などは定数倍が厳しいかもしれません。)