AT_abc265_g [ABC265G] 012 Inversion

题目描述

给定一个长度为 $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)$ 的逆序对数是满足 $1\leq i<j\leq M$ 且 $B_i>B_j$ 的整数对 $(i,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

输入 #1

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

输出 #1

3
4

输入输出样例 #2

输入 #2

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

输出 #2

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$
• 输入中的所有值均为整数

样例说明 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$。

由 ChatGPT 4.1 翻译