G - 012 Inversion Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

各要素が 0,1,2 のいずれかである長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。
Q 個のクエリを順に処理してください。各クエリは以下の 2 種類のいずれかです。

  • 1 L R：数列 (A_L,\ldots,A_R) の転倒数を出力する
  • 2 L R S T U： L\leq i \leq R を満たす各 i について、A_i が 0 なら S に、1 なら T に、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
  • 2 種類目のクエリにおいて、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

ここで i 番目のクエリを表す \rm Query_i は以下のいずれかの形式で与えられる。

1 L R

2 L R S T U

出力

1 種類目のクエリに対する答えを順に改行区切りで出力せよ。

入力例 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

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