012 Inversion

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定长度为 $N$ 的序列 $A$，每个元素均为 $0,1,2$。依次处理 $Q$ 个操作：

• 1 L R：输出子序列 $A_L,\ldots,A_R$ 的逆序对数。
• 2 L R S T U：对区间 $[L,R]$ 中的每个元素同时进行替换：$0$ 替换为 $S$，$1$ 替换为 $T$，$2$ 替换为 $U$。

逆序对是满足 $L\le i<j\le R$ 且 $A_i>A_j$ 的下标对 $(i,j)$。

输入格式

第一行包含两个整数 $N,Q$。

第二行包含 $N$ 个整数 $A_1,\ldots,A_N$。

接下来 $Q$ 行，每行是一条上述格式的操作。

输出格式

对每个第一类操作输出一行答案。

样例输入 1

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

样例输出 1

3
4

样例输入 2

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

样例输出 2

0
0

数据范围

对于全部数据，$1\le N,Q\le10^5$，$0\le A_i,S,T,U\le2$，$1\le L\le R\le N$。