102656: [AtCoder]ABC265 G - 012 Inversion
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $600$ points
Problem Statement
You are given a sequence $A=(A_1,\ldots,A_N)$ of length $N$. Each element is $0$, $1$, or $2$.
Process $Q$ queries in order. Each query is of one of the following kinds:
1 L R: print the inversion number of the sequence $(A_L,\ldots,A_R)$.2 L R S T U: for each $i$ such that $L\leq i \leq R$, if $A_i$ is $0$, replace it with $S$; if $A_i$ is $1$, replace it with $T$; if $A_i$ is $2$, replace it with $U$.
What is the inversion number?
The inversion number of a sequence $B = (B_1, \ldots, B_M)$ is the number of pairs of integers $(i, j)$ $(1 \leq i < j \leq M)$ such that $B_i > B_j$.Constraints
- $1 \leq N \leq 10^5$
- $0 \leq A_i \leq 2$
- $1\leq Q\leq 10^5$
- In each query, $1\leq L \leq R \leq N$.
- In each query of the second kind, $0\leq S,T,U \leq 2$.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $Q$ $A_1$ $A_2$ $\ldots$ $A_N$ $\rm Query_1$ $\rm Query_2$ $\vdots$ $\rm Query_Q$
$\rm Query_i$ denotes the $i$-th query, which is in one of the following formats:
$1$ $L$ $R$
$2$ $L$ $R$ $S$ $T$ $U$
Output
Print the responses to the queries of the first kind in the given order, separated by newlines.
Sample Input 1
5 3 2 0 2 1 0 1 2 5 2 2 4 2 1 0 1 2 5
Sample Output 1
3 4
Initially, $A=(2,0,2,1,0)$.
- In the $1$-st query, print the inversion number $3$ of $(A_2,A_3,A_4,A_5)=(0,2,1,0)$.
- The $2$-nd query makes $A=(2,2,0,1,0)$.
- In the $3$-rd query, print the inversion number $4$ of $(A_2,A_3,A_4,A_5)=(2,0,1,0)$.
Sample Input 2
3 3 0 1 2 1 1 1 2 1 3 0 0 0 1 1 3
Sample Output 2
0 0
Input
题意翻译
有一个元素全为 $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$。Output
分数：$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)$ 的逆序数是满足 $(i, j)$ $(1 \leq i < j \leq M)$ 的整数对的数量，其中 $B_i > B_j$。约束
- $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$
输出
按顺序以换行符分隔的方式打印对第一类查询的响应。
样例输入 1
5 3 2 0 2 1 0 1 2 5 2 2 4 2 1 0 1 2 5
样例输出 1
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$。
样例输入 2
3 3 0 1 2 1 1 1 2 1 3 0 0 0 1 1 3
样例输出 2
0 0