012 逆序对

题目描述

给定一个长度为 $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 \le i \le R$ 的每个 $i$，若 $A_i$ 为 $0$，则替换为 $S$；若 $A_i$ 为 $1$，则替换为 $T$；若 $A_i$ 为 $2$，则替换为 $U$。

什么是逆序对数？ 序列 $B = (B_1, \ldots, B_M)$ 的逆序对数，是满足 $1 \le i \lt j \le M$ 且 $B_i \gt B_j$ 的整数对 $(i, j)$ 的个数。

输入格式

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

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$\mathrm{Query}_1$
$\mathrm{Query}_2$
$\vdots$
$\mathrm{Query}_Q$

其中 $\mathrm{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)$。

第 $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$。

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

0
0

数据范围

• $1 \le N \le 10^5$
• $0 \le A_i \le 2$
• $1 \le Q \le 10^5$
• 在每个查询中，$1 \le L \le R \le N$
• 在第二类查询中，$0 \le S,T,U \le 2$
• 输入中的所有值均为整数