P4344 [SHOI2015] Brainhole Treatment Device

The inventor SHTSC, who once created the automatic problem-solving machine, has unveiled his new invention: the Brainhole Treatment Device — a mysterious apparatus that can treat the ever-enlarging “brainholes” caused by his inventions. For simplicity, we regard the brain as a 01 sequence. $1$ means the tissue at that position is working normally, and $0$ means it is a brainhole. ```cpp 1 0 1 0 0 0 1 1 1 0 ``` The basic principle for repairing a certain brainhole is to excavate another contiguous region and use the normal tissue from it to fill the hole. (So is the brainhole treatment device actually a treatment device for brainholes?) For example, if we use positions $8$ to $10$ to repair the hole from positions $1$ to $4$, we get: ```cpp 1 1 1 1 0 0 1 0 0 0 ``` If we then use positions $1$ to $4$ to repair positions $8$ to $10$: ```cpp 0 0 0 0 0 0 1 1 1 1 ``` This is because the Brainhole Treatment Device discards any excess tissue. If we then use positions $7$ to $10$ to fill positions $1$ to $6$: ```cpp 1 1 1 1 0 0 0 0 0 0 ``` This is because if the excavated normal tissue is not enough, the device only fills the brainhole as much as possible starting from the earlier positions (smaller indices). Assume that initially SHTSC has no brainholes. Given a sequence of digging and treatment operations, you need to answer online: within a given interval of the brain, what is the size of the largest contiguous brainhole.

The first line contains two integers $n, m$, meaning SHTSC’s brain is divided into $n$ contiguous regions numbered from $1$ to $n$, and there are $m$ operations. Each of the following $m$ lines is in one of the following three formats: * $0\quad l\quad r$: SHTSC digs a brainhole covering the range $[l, r]$. * $1\quad l_0\quad r_0\quad l_1\quad r_1$: SHTSC performs one treatment, using the normal tissue from $l_0$ to $r_0$ to repair the brainholes from $l_1$ to $r_1$. * $2\quad l\quad r$: SHTSC asks for the size of the largest brainhole within the interval $[l, r]$. All the above intervals lie within $[1, n]$.

For each query, output one line with one integer, the size of the largest contiguous brainhole within the query interval.

For $20\%$ of the testdata, $n, m \leq 100$. For $50\%$ of the testdata, $n, m \leq 20000$. For $100\%$ of the testdata, $n, m \leq 200000$. Translated by ChatGPT 5