L - マンションの改築 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

1 から N の番号がついたマンションが番号の昇順で一列に並んでいます。 はじめ、マンション i の高さは h_i です。

Q 回の操作が順番に行われます。i 回目の操作の種類は t_{i} で表され、その内容は以下の通りです。

  • t_i=1 のとき: 整数 v_i が与えられる。番号が奇数であるような全てのマンションの高さを v_i だけ増やす。
  • t_i=2 のとき: 整数 v_i が与えられる。番号が偶数であるような全てのマンションの高さを v_i だけ増やす。
  • t_i=3 のとき: 整数 u_i,v_i が与えられる。マンション u_i の高さを v_i だけ増やす。

それぞれの操作が終わった時点で、1 \leq i < N を満たす整数 i のうち、マンション i と i+1 の操作終了時点での高さが等しいようなものの個数を求めてください。

制約

  • 与えられる入力は全て整数
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq h_i, v_i \leq 10^9
  • t_i は 1,2,3 のいずれか
  • 1 \leq u_i \leq N

入力

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

N Q
h_1 h_2 \cdots h_N
\mathrm{Query}_{1}
\vdots
\mathrm{Query}_{Q}

\mathrm{Query}_{i} は以下の 3 つのいずれかである。

1 v_i
  • これは t_i=1 として操作を行うことを表す。
2 v_i
  • これは t_i=2 として操作を行うことを表す。
3 u_i v_i
  • これは t_i=3 として操作を行うことを表す。

出力

Q 行出力せよ。q 行目では、q 回の操作後、1 \leq i < N を満たす整数 i のうち、マンション i と i+1 の操作終了時点での高さが等しいようなものの個数を出力せよ。

入力例 1

4 2
10 20 30 20
1 10
3 4 20

出力例 1

1
2
  • はじめ、マンション 1,2,3,4 の高さはそれぞれ 10,20,30,20 です。
  • 1 回目の操作により、番号が奇数であるようなマンションの高さが変化し、それぞれの高さは 20,20,40,20 へと変化します。
    • マンション i と i+1 の高さが等しいような整数 i は 1 の 1 つです。
  • 2 回目の操作により、番号 4 のマンションの高さが変化し、それぞれの高さは 20,20,40,40 へと変化します。
    • マンション i と i+1 の高さが等しいような整数 i は 1,3 の 2 つです。

入力例 2

10 20
108 112 112 110 110 109 108 110 111 112
3 4 2
1 1
3 9 1
3 4 2
2 1
1 1
3 7 2
2 1
3 8 2
1 1
2 1
1 1
3 10 2
3 6 1
2 1
3 7 1
1 1
2 1
3 3 2
3 3 2

出力例 2

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

Score : 6 points

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are N apartments numbered 1 through N, standing in a row in this order. Initially, the height of Apartment i is h_i.

Q operations will be done sequentially. The type of the i-th operation is represented by t_{i}, as follows:

  • If t_i=1: Given an integer v_i, increase the height of every odd-numbered apartment (Apartment 1, 3, ...) by v_i.
  • If t_i=2: Given an integer v_i, increase the height of every even-numbered apartment (Apartment 2, 4, ...) by v_i.
  • If t_i=2: Given integers u_i and v_i, increase the height of Apartment u_i apartment by v_i.

For each operation, find the number of integers i satisfying 1 \leq i < N such that the heights of Apartment i and Apartment i+1 are equal at the end of the operation.

Constraints

  • All values in input are integers.
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq h_i, v_i \leq 10^9
  • t_i is 1, 2, or 3.
  • 1 \leq u_i \leq N

Input

Input is given from Standard Input in the following format:

N Q
h_1 h_2 \cdots h_N
\mathrm{Query}_{1}
\vdots
\mathrm{Query}_{Q}

Here, \mathrm{Query}_{i} is one of the following:

1 v_i
  • This represents that the operation is performed with t_i=1.
2 v_i
  • This represents that the operation is performed with t_i=2.
3 u_i v_i
  • This represents that the operation is performed with t_i=3.

Output

Print Q lines. The q-th line should contain the number of integers i satisfying 1 \leq i < N such that the heights of Apartment i and Apartment i+1 are equal at the end of the q-th operation.

Sample Input 1

4 2
10 20 30 20
1 10
3 4 20

Sample Output 1

1
2
  • Initially, the heights of the apartments 1,2,3,4 are 10,20,30,20, respectively.
  • In the 1-st operation, the heights of the odd-numbered apartments change, resulting in the heights of the apartments being 20,20,40,20.
    • Now there is one integer i such that the heights of Apartment i and Apartment i+1 are equal: 1.
  • In the 2-nd operation, the height of Apartment 4 changes, resulting in the heights of the apartments being 20,20,40,40.
    • Now there are two integers i such that the heights of Apartment i and Apartment i+1 are equal: 1,3.

Sample Input 2

10 20
108 112 112 110 110 109 108 110 111 112
3 4 2
1 1
3 9 1
3 4 2
2 1
1 1
3 7 2
2 1
3 8 2
1 1
2 1
1 1
3 10 2
3 6 1
2 1
3 7 1
1 1
2 1
3 3 2
3 3 2

Sample Output 2

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