ACLPC L

from AtCoder Library Practice Contest ACLPC_L L - Lazy Segment Tree

• 
• 転倒数
• 二値の列に対して(0の個数, 1の個数, 転倒数)を対応づける。
  • この値は、2つの列を結合したものについて計算することがこの値だけからできる
    • (DPを構築する時のような気持ち)

:

f((a1, b1, c1), (a2, b2, c2)) = (a1 + a2, b1 + b2, c1 + c2 + b1 * a2)

- これは落ち着いて考えれば当たり前
    - 0の個数、1の個数に関しては単なる和
    - 転倒数は、それぞれの元々の転倒数に、結合によって増える量を足す
    - この結合によって増える量とは「転倒してる数のペア」がそれぞれの列に分かれてるものの個数なので「左の列の中の1の個数」に「右の列の中の0の個数」をかけたものになる
- この合成演算fは結合的であり単位元(0, 0, 0)を持つので[モノイド](/ja/%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89)である
    - 実際、群である: [二値文字列の転倒数が従う群構造 - Qiita](https://qiita.com/hamko/items/92660ac5aed9df4d346d)
- よってこの値はセグメント木の値域に使うことができる

• 作用は列のビット反転だが、この時に値はどうなるか
  • (y, x, x * y - z)
  • 異なる数値の組み合わせがx * yペアあって、うちzペアが転倒してる、反転させると残りが転倒ペアになる 余事象