AT_abc265_g [ABC265G] 012 Inversion

[problemUrl]: https://atcoder.jp/contests/abc265/tasks/abc265_g 各要素が $ 0,1,2 $ のいずれかである長さ $ N $ の数列 $ A=(A_1,\ldots,A_N) $ が与えられます。 $ Q $ 個のクエリを順に処理してください。各クエリは以下の $ 2 $ 種類のいずれかです。 - `1 L R`：数列 $ (A_L,\ldots,A_R) $ の転倒数を出力する - `2 L R S T U`： $ L\leq\ i\ \leq\ R $ を満たす各 $ i $ について、$ A_i $ が $ 0 $ なら $ S $ に、$ 1 $ なら $ T $ に、$ 2 $ なら $ U $ に置き換える 転倒数とは？ 数列 $ B\ =\ (B_1,\ \ldots,\ B_M) $ の転倒数とは、整数の組 $ (i,\ j) $ $ (1\ \leq\ i\ であって\ B_i\ >\ B_j $ を満たすものの個数です。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \rm\ Query_1 $ $ \rm\ Query_2 $ $ \vdots $ $ \rm\ Query_Q $ ここで $ i $ 番目のクエリを表す $ \rm\ Query_i $ は以下のいずれかの形式で与えられる。 > $ 1 $ $ L $ $ R $ > $ 2 $ $ L $ $ R $ $ S $ $ T $ $ U $

$ 1 $ 種類目のクエリに対する答えを順に改行区切りで出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 0\ \leq\ A_i\ \leq\ 2 $ - $ 1\leq\ Q\leq\ 10^5 $ - 各クエリにおいて、$ 1\leq\ L\ \leq\ R\ \leq\ N $ - $ 2 $ 種類目のクエリにおいて、$ 0\leq\ S,T,U\ \leq\ 2 $ - 入力に含まれる値は全て整数である ### Sample Explanation 1 最初 $ A=(2,0,2,1,0) $ です。 - $ 1 $ 番目のクエリにおいて、$ (A_2,A_3,A_4,A_5)=(0,2,1,0) $ の転倒数 $ 3 $ を出力します。 - $ 2 $ 番目のクエリを処理すると、$ A=(2,2,0,1,0) $ となります。 - $ 3 $ 番目のクエリにおいて、$ (A_2,A_3,A_4,A_5)=(2,0,1,0) $ の転倒数 $ 4 $ を出力します。