当前没有测试数据。

G - 012 Inversion

得分：$600$ 分

问题描述

给定长度为 $N$ 的序列 $A=(A_1,\ldots,A_N)$。每个元素都是 $0$、$1$ 或 $2$。
按照顺序处理 $Q$ 个查询。每个查询有以下两种类型之一：

• 1 L R：输出序列 $(A_L,\ldots,A_R)$ 的逆序对个数。
• 2 L R S T U：对于每个满足 $L\leq i \leq R$ 的 $i$，如果 $A_i$ 是 $0$，则将其替换为 $S$；如果 $A_i$ 是 $1$，则将其替换为 $T$；如果 $A_i$ 是 $2$，则将其替换为 $U$。

什么是逆序对个数？

序列 $B = (B_1, \ldots, B_M)$ 的逆序对个数是满足条件 $B_i > B_j$ 的整数对 $(i, j)$ 的个数（$1 \leq i < j \leq M$）。

约束条件

• $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$。
• 在第二类查询中，$0\leq S,T,U \leq 2$。
• 输入中的所有值都是整数。

---

输入

输入以以下格式从标准输入给出：

$N$ $Q$

$A_1$ $A_2$ $\ldots$ $A_N$

$\rm Query_1$

$\rm Query_2$

$\vdots$

$\rm Query_Q$

$\rm Query_i$ 表示第 $i$ 个查询，它有以下两种格式之一：

``` $1$ $L$ $R$ ``` ``` $2$ $L$ $R$ $S$ $T$ $U$ ```

输出

按照给定顺序，每行输出一个第一类查询的结果。

---

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

3
4

初始时，$A=(2,0,2,1,0)$。

• 在第一个查询中，输出 $(A_2,A_3,A_4,A_5)=(0,2,1,0)$ 的逆序对个数 $3$。
• 第二个查询将 $A$ 变为 $(2,2,0,1,0)$。
• 在第三个查询中，输出 $(A_2,A_3,A_4,A_5)=(2,0,1,0)$ 的逆序对个数 $4$。

---

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

0
0