题目描述

各要素が $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$ 種類目のクエリに対する答えを順に改行区切りで出力せよ。

题目大意

有一个元素全为 $0,1$ 或 $2$ 的数列 $A = (A_1,A_2,\ldots,A_n)$。现在有两种操作：

1. 1 L R：询问区间 $[L,R]$ 内的逆序对数量；

2. 2 L R S T U：将区间 $[L,R]$ 内的所有 $0$ 改为 $S$，$1$ 改为 $T$，$2$ 改为 $U$。

5 3
2 0 2 1 0
1 2 5
2 2 4 2 1 0
1 2 5

3
4

3 3
0 1 2
1 1 1
2 1 3 0 0 0
1 1 3

0
0

提示

制約

• $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$ を出力します。