#P7825. 「RdOI R3」VSQ

「RdOI R3」VSQ

题目描述

xx 为一个长度不小于 220101 串,如果 xx 的所有长度为 22 的子串的异或和均为 11,则 xx 为一个「VS 串」。

你需要维护一个长度为 nn0101aa,支持以下操作:

$$\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} $$

输入格式

第一行两个整数 n,mn,m,表示 0101 串长度与操作个数。
第二行 nn 个整数,表示 a1,a2,,ana_1,a_2,\cdots,a_n
接下来 mm 行,每行三或四个整数 op,l,r(,k)op, l, r(,k),表示一次操作。

输出格式

对于每个查询操作,输出一行一个整数,表示其对应的答案。

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
2
3
5
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
1
3
2
0
1
3
2
2
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
4
0
1
1
3
2

提示

样例解释

样例 #1

操作次数 输入内容 零一串 答案
00 // 0110101101 //
11 0 1 2 0010100101
22 2 1 5 1101011010
33 3 1 5 3 22
44 2 1 3 0011000110 //
55 2 2 3 0101001010
66 3 1 5 3 33
77 4 1 5 55

数据范围

本题采用捆绑测试。

对于所有数据,有 0op40\le op \le 41lrn3×1051 \le l \le r \le n\le3\times10^53kn3 \le k \le n1m5×1051\le m \le 5 \times 10^5

subtask 分值 4n,m4\le n,m \le 时间限制 特殊性质
11 1010 10310^3 300300 ms
22 1515 10510^5 10001000 ms 没有 0,1,20,1,2 操作
33 20002000 ms 没有 33 操作
44 op,l,r,aiop,l,r,a_i 在其数据范围内等概率随机生成
55 30003000 ms k=3k=3
66 1010
77 2020 5×1055\times10^5 20002000 ms n3×105n\le3\times10^5

本题可能略微卡常。
这样设计时间限制是为了让测试点总时间限制在 120s 以内并且卡掉错误算法。