P7825 "RdOI R3" VSQ

Let $x$ be a $01$ string with length at least $2$. If the XOR of every length $2$ substring of $x$ is $1$, then $x$ is called a "VS string". You need to maintain a $01$ string $a$ of length $n$, supporting the following operations: $$ \def\arraystretch{1.5} \begin{array}{|c|c|} \hline \textbf{Format} & \textbf{Description} \cr\hline \texttt{0 l r} & \text{Fill the interval }[l,r]\text{ with }0 \cr\hline \texttt{1 l r}& \text{Fill the interval }[l,r]\text{ with }1 \cr\hline \texttt{2 l r}& \text{Flip every bit in }[l,r]\text{, i.e., }1\text{ becomes }0\text{ and }0\text{ becomes }1 \cr\hline \texttt{3 l r k} & \text{Query how many substrings of length }k\text{ in }[l,r]\text{ are "VS strings"} \cr\hline \texttt{4 l r} & {\def\arraystretch{1}\begin{array}{c} \text{Query the length of the longest "VS string" within }[l,r]\text{,}\\\text{and output }1\text{ if no such substring exists in the interval} \end{array}} \cr\hline \end{array} $$

The first line contains two integers $n,m$, representing the length of the $01$ string and the number of operations. The second line contains $n$ integers, representing $a_1,a_2,\cdots,a_n$. The next $m$ lines each contain three or four integers $op, l, r(,k)$, representing one operation.

For each query operation, output one integer per line, representing the corresponding answer.

### Sample Explanation #### Sample #1 |Number of operations|Input content|$01$ string|Answer| |-|-|-|-| |$0$|$/$|$01101$|$/$| |$1$|`0 1 2`|$00101$|$/$| |$2$|`2 1 5`|$11010$|$/$| |$3$|`3 1 5 3`|$11010$|$2$| |$4$|`2 1 3`|$00110$|$/$| |$5$|`2 2 3`|$01010$|$/$| |$6$|`3 1 5 3`|$01010$|$3$| |$7$|`4 1 5`|$01010$|$5$| --- ### Constraints **This problem uses bundled testdata.** For all testdata, $0\le op \le 4$, $1 \le l \le r \le n\le3\times10^5$, $3 \le k \le n$, $1\le m \le 5 \times 10^5$. | subtask | Score | $4\le n,m \le$ | Time limit | Special property | | ------- | ---- | -------------- | ---------- | ---------------- | | $1$ | $10$ | $10^3$ | $300$ ms | None | | $2$ | $15$ | $10^5$ | $1000$ ms | No operations $0,1,2$ | | $3$ | $15$ | $10^5$ | $2000$ ms | No operation $3$ | | $4$ | $15$ | $10^5$ | $2000$ ms | $op,l,r,a_i$ are generated uniformly at random within their ranges | | $5$ | $15$ | $10^5$ | $3000$ ms | $k=3$ | | $6$ | $10$ | $10^5$ | $3000$ ms | None | | $7$ | $20$ | $5\times10^5$ | $2000$ ms | $n\le3\times10^5$ | This problem may be slightly strict on constant factors. The time limits are designed to keep the total time limit of all test points within $120$s and to eliminate incorrect algorithms. Translated by ChatGPT 5