Takoyaki and Flip

AtCoder

IDabc441_g

Time2000ms

Memory256MB

Difficulty—

$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. [samples]

Samples

Input #1

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.
![image](https://img.atcoder.jp/abc441/5a1f8a0f9bdb43a16c4f458213f3b8e7.png)
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.

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

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.

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

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Takoyaki and Flip",
    "description": {
      "content": "$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 takoy",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc441_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$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 takoy...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments