連続する同じ値の区間を管理することを考えます。 この区間の数はクエリによってどう変化するでしょうか？

初期状態ではこのような区間の数は高々 \(N\) 個です。 クエリ \((l, r, x)\) を一つ処理する際、std::set 等の連想コンテナを用いることで区間 \([l, r]\) と交わる区間のみを列挙することが可能です。これらの区間に対して、

• 完全に包含される

  • この区間を消去する。

• 一部重なる

  • この区間を消去し、残った部分を新しく追加する。

という処理を行います。一回のクエリで追加される新しい区間は高々 \(3\) 個です。

また、削除をする回数は明らかに区間を追加した回数より少ないです。

よって、全体で区間を追加する回数は \(O\left(N + Q\right)\) 削除する回数も同様に \(O\left(N + Q\right)\) であることがわかります。

要素 \(i\) の数列の中での頻度を \(C_i\) と置くと求める答えは \(\displaystyle\sum \dfrac{C_i \times (C_i - 1)}{2} \) です。

区間の追加/削除で影響を受ける要素は \(1\) つであることから、それらの操作に対するこの値の差分は \(O\left(1\right)\) で計算することができます。

よって、全体での計算量は \(O\left(\left(N + Q\right) \log \left(N + Q\right)\right)\) です。

追記

上の処理をする構造体を書いてみたのでよかったら使ってください！ リンク