1111

t1

t2

• 用差分数组 $a$ 和 $b$ 表示 $X$ 和 $Y$ 的边界：
  • $a[i] = 1$ 表示 $X_i \neq X_{i-1}$
  • $b[i] = 1$ 表示 $Y_i \neq Y_{i-1}$

$X$ 能转换为 $Y$ 当：

• 对于任意前缀 $[1, k]$，$X$ 的边界数 $\geq$ $Y$ 的边界数。
  即：$\forall k \in [1, n], \sum a[i] \geq \sum b[i]$
• $X$ 和 $Y$ 的最后一个字符在变换后相同
  等价于：$\bigoplus_1^n a_i = \bigoplus_1^n b_i$

• 前缀： $\min_{k=1}^n d[k] \geq 0$
• 整体： 维护 $\bigoplus_1^n a_i$ 和 $\bigoplus_1^n b_i$

当翻转原始字符串的第 $p$ 个字符时：

1. 翻转 $a[p]$
2. 更新线段树：
   • 翻转 $a[p]$：对区间 $[1, p]$ 加 $\Delta$（$\Delta = 1$ 如果 $a[p] \to 1$ ，否则为$-1$）
   • 翻转 $a[p+1]$
3. 更新 $ca$：$ca \leftarrow ca \oplus 1$（如果 $p=n$）

• 最小值 $\geq 0$
• $ca = cb$
  即可。

cf1763c

• $n>4$时，$ans=\max a_i$
  考虑1 1 4 5 1 4 -> 1 1 4 5 3 3 -> 1 1 4 5 0 0(造0)
  ->1 1 4 5 5 5-> 0 0 4 5 5 5 -> 5 5 5 5 5 5
  在右断点造0，把max传播到右端点，在对左端点做一遍即可。
• $n=2$ , $ans=\max(a_1+a_2,2*|a_1-a_2|)$
  显然只有两种情况。
• $n=3,\max \in \{a_1,a_3\}$ : 同$n>3$
• $n=3,\max = a_2$:
  • $(1,3)$ : $3|a_3-a_1| \to ans$
  • $(1,2)$ : $3\cdot\max(|a_2-a_1|,a_3) \to ans$
    做完后有$|a_2-a_1|,a_3$两个值，可以取最大的。
  • $(2,3)$ : $3\cdot\max(|a_3-a_2|,a_1) \to ans$

cf2124e

• $\sum a_i = 1(\bmod 2)$