ABC242G Range Pairing Query

解説AC

問題へのリンク
解説へのリンク

初Mo's Algotithm
Mo's Algorithmの適用可能条件は以下の通りです。

1. 配列が不変
2. クエリ先読み可
3. 区間を+1, -1ずつ伸縮しても値の再計算が容易

1,2は満たすので3が満たせればよく、以下の方法で容易に計算できることがわかります。

:区間内のの出現数
とします。最大のペア数は、以下のように計算できます。

• 区間を伸長した時
  新たに区間内となるものをとすると、伸長前にが奇数なら、ペアを新たに作れるのでを+1する。

• 区間を短縮した時
  新たに区間外となるものをとすると、短縮前にが偶数なら、ペアが1つ減るのでを-1する。

よって、Mo's Algorithmによりで解けます。

Mo's Algorithmは公式解説のリンクなど見れば良いですが、自分でも別記事に簡単にまとめました。
Mo's Algorithm

提出コード