P7825 「RdOI R3」VSQ

设 $x$ 为一个长度不小于 $2$ 的 $01$ 串，如果 $x$ 的所有长度为 $2$ 的子串的异或和均为 $1$，则 $x$ 为一个「VS 串」。 你需要维护一个长度为 $n$ 的 $01$ 串 $a$，支持以下操作： $$ \def\arraystretch{1.5} \begin{array}{|c|c|} \hline \textbf{格式} & \textbf{说明} \cr\hline \texttt{0 l r} & \text{将区间 }[l,r]\text{ 填充为 }0 \cr\hline \texttt{1 l r}& \text{将区间 }[l,r]\text{ 填充为 }1 \cr\hline \texttt{2 l r}& \text{将区间 }[l,r]\text{ 中的每个数取反，即 }1\text{ 变 } 0\text{，}0\text{ 变 }1 \cr\hline \texttt{3 l r k} & \text{查询}[l,r]\text{ 区间中有多少个长度为 }k\text{ 的子串是「VS 串」} \cr\hline \texttt{4 l r} & {\def\arraystretch{1}\begin{array}{c} \text{查询 }[l,r]\text{ 区间内最长的「VS 串」的长度，}\\\text{如果区间内不存在这样的子串则输出 }1 \end{array}} \cr\hline \end{array} $$

无

无

### 样例解释 #### 样例 #1 |操作次数|输入内容|零一串|答案| |-|-|-|-| |$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$| --- ### 数据范围 **本题采用捆绑测试。** 对于所有数据，有 $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 | 分值 | $4\le n,m \le$ |时间限制| 特殊性质 | | ------- | ---- | -------------- |-------| --------------------------- | | $1$ | $10$ | $10^3$ |$300$ ms| 无 | | $2$ | $15$ | $10^5$ |$1000$ ms| 没有 $0,1,2$ 操作 | | $3$ | $15$ | $10^5$ |$2000$ ms| 没有 $3$ 操作 | | $4$ | $15$ | $10^5$ |$2000$ ms| $op,l,r,a_i$ 在其数据范围内等概率随机生成 | | $5$ | $15$ | $10^5$ |$3000$ ms| $k=3$ | | $6$ | $10$ | $10^5$ |$3000$ ms| 无 | | $7$ | $20$ | $5\times10^5$ |$2000$ ms| $n\le3\times10^5$ | 本题可能略微卡常。 这样设计时间限制是为了让测试点总时间限制在 120s 以内并且卡掉错误算法。