D - Inversion Count Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 3 点

問題文

0,1,2 からなる長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

クエリを Q 個処理してください。クエリは以下の 2 種類のいずれかです。

  • 1 i x：A_i を x に変更する。
  • 2 l r：数列 (A_l,A_{l+1},\ldots,A_r) の転倒数を出力する。

ここで、長さ k の数列 B=(B_1,B_2,\ldots,B_k) の 転倒数 とは、 1 \leq i \lt j \leq k かつ B_i \gt B_j を満たす整数の組 (i,j) の個数です。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 2
  • 1 種類目のクエリについて、1 \leq i \leq N, 0 \leq x \leq 2
  • 2 種類目のクエリについて、1 \leq l \leq r \leq N
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

各クエリは以下のいずれかの形式で与えられる。

1 i x

2 l r

出力

2 種類目のクエリの個数を q として、q 行出力せよ。j 行目には、j 番目の 2 種類目のクエリに対する答えを出力せよ。

入力例 1

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

出力例 1

5
0
2
4

はじめ、A=(2,0,1,2,0) です。

3 番目のクエリを処理した後、A=(2,2,1,2,0) となります。

入力例 2

6 6
0 2 1 0 2 1
2 1 6
1 1 2
2 1 4
1 4 2
2 3 6
2 4 4

出力例 2

5
5
2
0

Score: 3 points

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of 0,1,2.

Process Q queries. Each query is of one of the following 2 types:

  • 1 i x: Change A_i to x.
  • 2 l r: Print the inversion count of the sequence (A_l,A_{l+1},\ldots,A_r).

Here, the inversion count of a sequence B=(B_1,B_2,\ldots,B_k) of length k is the number of pairs of integers (i,j) satisfying 1 \leq i \lt j \leq k and B_i \gt B_j.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 2
  • For type 1 queries, 1 \leq i \leq N, 0 \leq x \leq 2
  • For type 2 queries, 1 \leq l \leq r \leq N
  • All numerical values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Each query is given in one of the following formats:

1 i x

2 l r

Output

Let q be the number of type 2 queries. Print q lines. The j-th line should contain the answer to the j-th type 2 query.

Sample Input 1

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

Sample Output 1

5
0
2
4

Initially, A=(2,0,1,2,0).

After processing query 3, A=(2,2,1,2,0).

Sample Input 2

6 6
0 2 1 0 2 1
2 1 6
1 1 2
2 1 4
1 4 2
2 3 6
2 4 4

Sample Output 2

5
5
2
0