P13274 [NOI2025] 三目运算符

ternary.cpp / 2 s / 512 MiB

对于一个长度为 $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$ 表示 **二进制按位异或**。

该样例共包含两组测试数据。 对于第一组测试数据： - 初始时，$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 ~ 3 的约束条件。 **【样例 3】** 见选手目录下的 ternary/ternary3.in 与 ternary/ternary3.ans。 该样例满足测试点 4 ~ 6 的约束条件。 **【样例 4】** 见选手目录下的 ternary/ternary4.in 与 ternary/ternary4.ans。 该样例满足测试点 13、14 的约束条件。 **【样例 5】** 见选手目录下的 ternary/ternary5.in 与 ternary/ternary5.ans。 该样例满足测试点 17 ~ 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$。 ::cute-table{tuack} | 测试点编号 | $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](https://qoj.ac/contest/2316/problem/13082)。