题目描述
Problem Description
Let $x$ be a binary string of length not less than $2$. If the XOR sum of all length-2 substrings of $x$ is $1$, then $x$ is a "VS string".
You need to maintain a binary string $a$ of length $n$ and support 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{Invert each number in the interval }[l,r]\text{, i.e., }1\text{ becomes }0\text{, and }0\text{ becomes }1 \cr\hline \texttt{3 l r k} & \text{Query the number of length-$k$ substrings in the interval }[l,r]\text{ that are "VS strings"} \cr\hline \texttt{4 l r} & \text{Query the length of the longest "VS string" in the interval }[l,r]\text{, if no such substring exists, output }1 \cr\hline \end{array} $$
Input Format
The first line contains two integers $n, m$, representing the length of the binary 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 containing three or four integers $op, l, r(, k)$, represent an operation.
Output Format
For each query operation, output a line with an integer representing the corresponding answer.
Sample Input and Output
Input Sample #1
5 7
0 1 1 0 1
0 1 2
2 1 5
3 1 5 3
2 1 3
2 2 3
3 1 5 3
4 1 5
Output Sample #1
2
3
5
Input Sample #2
10 9
0 1 1 0 1 1 0 1 1 0
3 1 5 3
4 2 9
4 1 4
3 4 10 4
3 4 10 3
4 1 5
4 9 10
4 4 6
4 5 9
Output Sample #2
1
3
2
0
1
3
2
2
3
Input Sample #3
10 10
0 0 0 1 0 0 0 1 0 0
2 7 10
4 6 9
3 2 9 7
1 6 7
4 10 10
1 1 3
3 4 7 3
4 2 8
1 6 9
4 5 6
Output Sample #3
4
0
1
1
3
2
Notes/Hints
Sample Explanation
Sample #1
| Operation Count | Input | Binary 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$ |
Data Range
This problem uses batched testing.
For all data, $0 \le op \le 4$, $1 \le l \le r \le n \le 3 \times 10^5$, $3 \le k \le n$, $1 \le m \le 5 \times 10^5$.
| Subtask | Score | $4 \le n, m \le$ | Time Limit | Special Conditions |
|---|---|---|---|---|
| $1$ | $10$ | $10^3$ | $300$ ms | None |
| $2$ | $15$ | $10^5$ | $1000$ ms | No $0, 1, 2$ operations |
| $3$ | $15$ | $10^5$ | $2000$ ms | No $3$ operation |
| $4$ | $15$ | $10^5$ | $2000$ ms | $op, l, r, a_i$ are randomly generated within their data ranges |
| $5$ | $15$ | $10^5$ | $3000$ ms | $k = 3$ |
| $6$ | $10$ | $10^5$ | $3000$ ms | None |
| $7$ | $20$ | $5 \times 10^5$ | $2000$ ms | $n \le 3 \times 10^5$ |
This problem may have slightly strict time limits.
The time limits are designed to keep the total test time within 120 seconds and to filter out incorrect algorithms.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分