G - Takoyaki and Flip Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 575 点

問題文

N 枚の皿が左から右に一直線状に並んでいます。 左から i 番目 (1\le i\le N) の皿を皿 i と呼ぶことにします。 はじめ、どの皿も表を上にして置かれており、どの皿にもたこ焼きが置かれていません。

次の 3 種類のクエリを合計 Q 回処理してください。

  • タイプ 1：整数 L,R,X が与えられる。i=L,L+1,\ldots,R に対して、皿 i が表を上にして置かれているなら、皿 i にたこ焼きを X 個置く。
  • タイプ 2：整数 L,R が与えられる。i=L,L+1,\ldots,R に対して、皿 i にたこ焼きが 1 個以上置かれていた場合、皿 i に置かれているたこ焼きをすべて食べる。皿 i をひっくり返す（皿が表を上にして置かれている場合裏を上にして置き、そうでない場合表を上にして置く）。
  • タイプ 3：整数 L,R が与えられる。皿 L, 皿 L+1,\ldots, 皿 R にわたる、置かれているたこ焼きの個数の最大値を出力する。

制約

  • 1\le N\le2\times10 ^ 5
  • 1\le Q\le2\times10 ^ 5
  • すべてのクエリにおいて、1\le L\le R\le N
  • タイプ 1 のクエリにおいて、1\le X\le10 ^ 9
  • タイプ 3 のクエリが存在する。
  • 入力はすべて整数

入力

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

N Q
\mathrm{query} _ 1
\mathrm{query} _ 2
\vdots
\mathrm{query} _ Q

ここで、\mathrm{query} _ i は i 番目 (1\le i\le Q) のクエリを表し、次のどちらかの形式で与えられる。

t L R X

t L R

これらは、i 番目のクエリがタイプ t のクエリで、与えられる整数が L,R,X もしくは L,R であることを表す。 タイプ 1 のクエリは前者の形式で、それ以外のクエリは後者の形式で与えられる。

出力

タイプ 3 のクエリの個数を q として、q 行にわたって出力せよ。 i 行目 (1\le i\le q) には、タイプ 3 のクエリのうち先頭から i 番目のものに対する答えを出力せよ。

入力例 1

6 6
1 3 5 4
3 2 3
1 1 6 2
2 3 4
3 1 6
3 2 3

出力例 1

4
6
2

各クエリの時点で、それぞれの皿の状態とその上に置かれているたこ焼きの個数は以下の図のようになります。

2 番目のクエリの時点では、皿 2 と皿 3 のうち置かれているたこ焼きの個数がより多いのは皿 3 です。 よって、1 行目には皿 3 に置かれているたこ焼きの個数である 4 を出力してください。

5 番目のクエリの時点では、皿 1, 皿 2,\ldots, 皿 6 のうち置かれているたこ焼きの個数が最も多いのは皿 5 です。 よって、2 行目には皿 5 に置かれているたこ焼きの個数である 6 を出力してください。

6 番目のクエリの時点では、皿 2 と皿 3 のうち置かれているたこ焼きの個数がより多いのは皿 2 です。 よって、3 行目には皿 2 に置かれているたこ焼きの個数である 2 を出力してください。

入力例 2

2 8
1 1 2 1000000000
1 1 2 1000000000
2 2 2
1 1 2 1000000000
1 1 2 1000000000
1 1 2 1000000000
3 2 2
3 1 2

出力例 2

0
5000000000

裏を上にして置かれている皿にはひとつもたこ焼きは置かれないことに注意してください。

また、答えが 2 ^ {32} 以上になる場合があることに注意してください。

入力例 3

24 30
1 11 24 4326
1 4 16 1149
1 14 20 2331
1 12 14 8930
1 22 23 6989
3 15 20
3 10 19
1 3 12 7988
1 18 23 8450
3 9 19
3 13 15
2 8 15
2 9 14
1 11 17 4062
1 6 15 1721
3 7 13
1 11 20 8541
1 8 10 3748
1 1 17 3252
2 9 23
2 1 23
3 2 22
1 5 23 7468
3 1 12
3 12 19
2 6 24
3 2 14
3 1 15
2 15 19
3 2 14

出力例 3

7806
16736
22393
16736
10858
0
7468
7468
0
0
0

Score : 575 points

Problem Statement

N plates are arranged in a straight line from left to right. Let us call the i-th plate from the left (1\le i\le N) plate i. Initially, all plates are placed face-up, and no plates have takoyaki (octopus dumplings) on them.

Process a total of Q queries of the following three types:

  • Type 1: You are given integers L,R,X. For i=L,L+1,\ldots,R, if plate i is placed face-up, place X takoyaki on plate i.
  • Type 2: You are given integers L,R. For i=L,L+1,\ldots,R, if there is at least one takoyaki on plate i, eat all the takoyaki on plate i. Flip plate i (if the plate is placed face-up, place it face-down; otherwise, place it face-up).
  • Type 3: You are given integers L,R. Print the maximum number of takoyaki on one plate among plates L, L+1,\ldots, R.

Constraints

  • 1\le N\le2\times10 ^ 5
  • 1\le Q\le2\times10 ^ 5
  • In all queries, 1\le L\le R\le N.
  • In type 1 queries, 1\le X\le10 ^ 9.
  • There is at least one type 3 query.
  • All input values are integers.

Input

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

N Q
\mathrm{query} _ 1
\mathrm{query} _ 2
\vdots
\mathrm{query} _ Q

Here, \mathrm{query} _ i represents the i-th (1\le i\le Q) query and is given in one of the following formats:

t L R X

t L R

These indicate that the i-th query is of type t and the given integers are L,R,X or L,R. Type 1 queries are given in the former format, and other queries are given in the latter format.

Output

Let q be the number of type 3 queries. Print q lines. The i-th line (1\le i\le q) should contain the answer to the i-th type 3 query from the beginning.

Sample Input 1

6 6
1 3 5 4
3 2 3
1 1 6 2
2 3 4
3 1 6
3 2 3

Sample Output 1

4
6
2

At the time of each query, the state of each plate and the number of takoyaki on it are as shown in the figure below.

At the time of the second query, among plates 2 and 3, the one with more takoyaki is plate 3. Thus, print 4, the number of takoyaki on plate 3, on the first line.

At the time of the fifth query, among plates 1, 2,\ldots, 6, the one with the most takoyaki is plate 5. Thus, print 6, the number of takoyaki on plate 5, on the second line.

At the time of the sixth query, among plates 2 and 3, the one with more takoyaki is plate 2. Thus, print 2, the number of takoyaki on plate 2, on the third line.

Sample Input 2

2 8
1 1 2 1000000000
1 1 2 1000000000
2 2 2
1 1 2 1000000000
1 1 2 1000000000
1 1 2 1000000000
3 2 2
3 1 2

Sample Output 2

0
5000000000

Note that no takoyaki is placed on plates that are placed face-down.

Also, note that the answer may be 2 ^ {32} or more.

Sample Input 3

24 30
1 11 24 4326
1 4 16 1149
1 14 20 2331
1 12 14 8930
1 22 23 6989
3 15 20
3 10 19
1 3 12 7988
1 18 23 8450
3 9 19
3 13 15
2 8 15
2 9 14
1 11 17 4062
1 6 15 1721
3 7 13
1 11 20 8541
1 8 10 3748
1 1 17 3252
2 9 23
2 1 23
3 2 22
1 5 23 7468
3 1 12
3 12 19
2 6 24
3 2 14
3 1 15
2 15 19
3 2 14

Sample Output 3

7806
16736
22393
16736
10858
0
7468
7468
0
0
0