负责人

• SleepingCup

题目描述

对于一个长度为 $n$ ($n \geq 3$) 的 01 串 $S = s_1 \ldots s_n$，定义变换 $T = f(S) = t_1 \ldots t_n$ 如下：

$$t_i = \begin{cases} s_i, & i \leq 2, \\ s_i, & i \geq 3 \text{ 且 } s_{i-2} = 0, \\ s_{i-1}, & i \geq 3 \text{ 且 } s_{i-2} = 1. \end{cases}$$

定义变换 $f$ 的 不动点 如下：若 01 串 $T$ 满足 $f(T) = T$，则称 $T$ 为变换 $f$ 的不动点。

记 $f^k(S)$ 为 $S$ 经过 $k$ 次变换得到的串。特别地，记 $f^0(S) = S$。求最小的自然数 $k$，使得 $f^k(S)$ 为变换 $f$ 的不动点，即满足 $f^{k+1}(S) = f^k(S)$ 的最小的自然数 $k$。可以证明，一定存在自然数 $k$ 使得 $f^k(S)$ 为变换 $f$ 的不动点。

小 Z 觉得这个问题过于简单，因此他增加了 $q$ 次修改操作。第 $i$ ($1 \leq i \leq q$) 次修改会给定两个正整数 $l_i, r_i$ ($1 \leq l_i \leq r_i \leq n$)，然后将区间 $[l_i, r_i]$ 内的所有原有的 0 替换为 1，所有原有的 1 替换为 0。你需要对初始时及每次修改后的字符串 $S$，求出最小的自然数 $k$，使得 $f^k(S)$ 为变换 $f$ 的不动点。

输入格式

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c = 0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含两个正整数 $n, q$，分别表示 $S$ 的长度和修改次数。

第二行包含一个长度为 $n$ 的 01 串 $S = s_1 \ldots s_n$，表示初始时的字符串。

第 $i + 2$ ($1 \leq i \leq q$) 行包含两个正整数 $l_i, r_i$，表示一次修改操作。

输出格式

对于每组测试数据，设初始时的答案为 $k_0$，第 $i$ ($1 \leq i \leq q$) 次修改后的答案为 $k_i$，输出一行一个正整数，表示 $\oplus_{i=0}^{q} ((i + 1) \times k_i)$，其中 $\oplus$ 表示 二进制按位异或。

样例

0 2
5 2
11010
3 3
2 2
7 3
1010100
7 7
2 4
1 2

2
4

提示

【样例 1 解释】

该样例共包含两组测试数据。

对于第一组测试数据：

• 初始时，$S = 11010$，$f(S) = 11100$，$f^2(S) = 11110$，$f^3(S) = f^4(S) = 11111$，因此 $k_0 = 3$；
• 第一次操作后，$S = 11110$，$f(S) = f^2(S) = 11111$，因此 $k_1 = 1$；
• 第二次操作后，$S = 10110$，$f(S) = f^2(S) = 10011$，因此 $k_2 = 1$。

故答案为 $\bigoplus_{i=0}^{q} ((i+1) \times k_i) = (1 \times 3) \oplus (2 \times 1) \oplus (3 \times 1) = 3 \oplus 2 \oplus 3 = 2$。

对于第二组测试数据：

• 初始时，$S = 1010100$，$k_0 = 1$；
• 第一次操作后，$S = 1010101$，$k_1 = 1$；
• 第二次操作后，$S = 1101101$，$k_2 = 5$；
• 第三次操作后，$S = 0001101$，$k_3 = 2$。

故答案为 $\bigoplus_{i=0}^{q} ((i+1) \times k_i) = (1 \times 1) \oplus (2 \times 1) \oplus (3 \times 5) \oplus (4 \times 2) = 4$。

【样例 2】

见选手目录下的 ternary/ternary2.in 与 ternary/ternary2.ans。

该样例满足测试点 $1 \sim 3$ 的约束条件。

【样例 3】

见选手目录下的 ternary/ternary3.in 与 ternary/ternary3.ans。

该样例满足测试点 $4 \sim 6$ 的约束条件。

【样例 4】

见选手目录下的 ternary/ternary4.in 与 ternary/ternary4.ans。

该样例满足测试点 $13,14$ 的约束条件。

【样例 5】

见选手目录下的 ternary/ternary5.in 与 ternary/ternary5.ans。

该样例满足测试点 $17 \sim 19$ 的约束条件。

【数据范围】

设 $N, Q$ 分别为单个测试点内所有测试数据的 $n, q$ 的和。对于所有测试数据，保证：

• $1 \leq t \leq 5$;
• $3 \leq n \leq 4 \times 10^5$, $N \leq 8 \times 10^5$;
• $1 \leq q \leq 4 \times 10^5$, $Q \leq 8 \times 10^5$;
• 对于所有 $1 \leq i \leq n$, 均有 $s_i \in \{0, 1\}$;
• 对于所有 $1 \leq i \leq q$, 均有 $1 \leq l_i \leq r_i \leq n$。

测试点编号	$n, q \leq$	$N, Q \leq$	特殊性质
$1 \sim 3$	$200$	$10^3$	A
$4 \sim 6$			无
$7, 8$	$5,000$	$10^4$	A
$9 \sim 11$			无
$12$	$10^5$	$2 \times 10^5$	A
$13, 14$			B
$15, 16$			无
$17 \sim 19$	$4 \times 10^5$	$8 \times 10^5$	C
$20$			无

特殊性质 A: 保证初始时及每次修改后，存在整数 $p \in [2, n]$ 满足 $s_1 = s_2 = \cdots = s_p = 1$ 且 $s_{p+1} = \cdots = s_n = 0$。

特殊性质 B: 保证对于所有 $1 \leq i \leq q$, 均有 $l_i = 1$, $r_i = n$。

特殊性质 C: 保证对于所有 $1 \leq i \leq q$, 均有 $l_i = 1$, 且 $r_1 \leq r_2 \leq \cdots \leq r_q$。

附加文件来自于 QOJ。