A5082. [NOI2025] 三目运算符
编程题
提高+/省选-
知识点
题目描述
对于一个长度为 $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$ 的不动点。
$$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$，表示一次修改操作。
输入的第一行包含两个非负整数 $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$ 表示 **二进制按位异或**。
输入输出样例
输入 #1
0 2 5 2 11010 3 3 2 2 7 3 1010100 7 7 2 4 1 2
输出 #1
2 4
说明/提示
## 说明/提示
该样例共包含两组测试数据。
对于第一组测试数据：
- 初始时，$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】**
该样例满足测试点 1 ~ 3 的约束条件。
**【样例 3】**
该样例满足测试点 4 ~ 6 的约束条件。
**【样例 4】**
该样例满足测试点 13、14 的约束条件。
**【样例 5】**
该样例满足测试点 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$。
| 测试点编号 | $n, q \leq$ | $N, Q \leq$ | 特殊性质 |
| :-: | :-: | :-: | :-: |
| $1 \sim 3$ | $200$ | $10^3$ | A |
| $4 \sim 6$ | $200$ | $10^3$ | 无 |
| $7, 8$ | $5,000$ | $10^4$ | A |
| $9 \sim 11$ | $5,000$ | $10^4$ | 无 |
| $12$ | $10^5$ | $2 \times 10^5$ | A |
| $13, 14$ | $10^5$ | $2 \times 10^5$ | B |
| $15, 16$ | $10^5$ | $2 \times 10^5$ | 无 |
| $17 \sim 19$ | $4 \times 10^5$ | $8 \times 10^5$ | C |
| $20$ | $4 \times 10^5$ | $8 \times 10^5$ | 无 |
特殊性质 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$。
该样例共包含两组测试数据。
对于第一组测试数据：
- 初始时，$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】**
该样例满足测试点 1 ~ 3 的约束条件。
**【样例 3】**
该样例满足测试点 4 ~ 6 的约束条件。
**【样例 4】**
该样例满足测试点 13、14 的约束条件。
**【样例 5】**
该样例满足测试点 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$。
| 测试点编号 | $n, q \leq$ | $N, Q \leq$ | 特殊性质 |
| :-: | :-: | :-: | :-: |
| $1 \sim 3$ | $200$ | $10^3$ | A |
| $4 \sim 6$ | $200$ | $10^3$ | 无 |
| $7, 8$ | $5,000$ | $10^4$ | A |
| $9 \sim 11$ | $5,000$ | $10^4$ | 无 |
| $12$ | $10^5$ | $2 \times 10^5$ | A |
| $13, 14$ | $10^5$ | $2 \times 10^5$ | B |
| $15, 16$ | $10^5$ | $2 \times 10^5$ | 无 |
| $17 \sim 19$ | $4 \times 10^5$ | $8 \times 10^5$ | C |
| $20$ | $4 \times 10^5$ | $8 \times 10^5$ | 无 |
特殊性质 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$。