题目理解

给定两个长度为 $n$ 的 DNA 序列 $a$ 和 $b$（仅包含字符 A、T、C），定义修改操作为交换字符串中任意两个字符的位置。两个字符串的修改距离是指将一个字符串通过修改操作转换为另一个字符串所需的最少操作次数。如果无法转换，则修改距离为 $-1$。

现在有 $q$ 次询问，每次询问给出区间 $[x, y]$，要求计算子串 $a[x \ldots y]$ 和 $b[x \ldots y]$ 之间的修改距离。

---

关键观察

1. 可转换的充要条件

由于交换操作不改变字符的频率分布，因此两个子串可相互转换的必要前提是：对于每个字符 $ch \in \{\text{A}, \text{T}, \text{C}\}$，它在 $a[x \ldots y]$ 中的出现次数必须等于在 $b[x \ldots y]$ 中的出现次数。

2. 问题转化

将 $a$ 和 $b$ 在对应位置上字符不同的位置分为六种类型：

• $AT$：$a$ 为 A，$b$ 为 T
• $TA$：$a$ 为 T，$b$ 为 A
• $AC$：$a$ 为 A，$b$ 为 C
• $CA$：$a$ 为 C，$b$ 为 A
• $TC$：$a$ 为 T，$b$ 为 C
• $CT$：$a$ 为 C，$b$ 为 T

一次交换操作可以解决两处不匹配：

1. 直接配对：交换一个 $AT$ 和一个 $TA$，或一个 $AC$ 和一个 $CA$，或一个 $TC$ 和一个 $CT$，可以同时使这两个位置匹配。
2. 三元环调整：若某种类型有剩余，则必然形成一个三元环（如 $AT$、$CA$、$CT$ 各多出一个），需要通过两次交换解决这三个位置。

---

算法设计

1. 预处理

使用三维前缀和统计六种类型的数量：

定义数组 $pref[i][c_1][c_2]$ 表示前 $i$ 个位置中，满足 $a[j] = c_1$ 且 $b[j] = c_2$ 的位置数量（$c_1, c_2 \in \{0,1,2\}$，对应 A、T、C）。

// 字符映射
'A' -> 0, 'T' -> 1, 'C' -> 2

// 初始化前缀和
for i = 1 to n:
    pref[i][c1][c2] = pref[i-1][c1][c2]
    if a[i] == c1 && b[i] == c2:
        pref[i][c1][c2]++

2. 查询处理

对于每个询问 $[x, y]$：

步骤 1：计算六种类型的数量

利用前缀和快速计算：

• $AT = pref[y][0][1] - pref[x-1][0][1]$
• $TA = pref[y][1][0] - pref[x-1][1][0]$
• $AC = pref[y][0][2] - pref[x-1][0][2]$
• $CA = pref[y][2][0] - pref[x-1][2][0]$
• $TC = pref[y][1][2] - pref[x-1][1][2]$
• $CT = pref[y][2][1] - pref[x-1][2][1]$

步骤 2：检查可行性

验证三个字符的出现次数是否相等：

1. $AT + AC = TA + CA$ （A 的出现次数相等）
2. $TA + TC = AT + CT$ （T 的出现次数相等）
3. $CA + CT = AC + TC$ （C 的出现次数相等）

若任意条件不满足，则返回 $-1$。

步骤 3：计算最少交换次数

1. 直接配对：每对直接交换解决两个位置$$\text{pairs} = \min(AT, TA) + \min(AC, CA) + \min(TC, CT) $$
2. 三元环调整：剩余的不匹配形成三元环，每个三元环需要 $2$ 次交换$$\text{cycles} = 2 \times |AT - TA|$$

总交换次数为：

$$\text{ans} = \text{pairs} + \text{cycles}$$

---

算法正确性

1. 充要条件证明

必要性已如前述。充分性通过构造性算法证明：首先进行尽可能多的直接配对交换，然后剩余的不匹配位置必然满足 $|AT-TA| = |AC-CA| = |TC-CT|$，且可通过三元环交换解决。

2. 最少性证明

• 直接配对交换是最优的：一次交换解决两个不匹配位置。
• 三元环交换是最优的：三个不匹配位置至少需要两次交换（因为一次交换最多解决两个位置）。

---

复杂度分析

时间复杂度

• 预处理：$O(n)$，需要填充三维前缀和数组（常数 $9$）。
• 每次查询：$O(1)$，只需常数次前缀和查询与计算。

总时间复杂度：$O(n + q)$，完全满足 $n, q \leq 10^5$ 的限制。

空间复杂度

• 前缀和数组：$O(n)$，使用 $n \times 3 \times 3$ 的数组。
• 其他辅助数组：$O(n)$。

---

代码实现要点

1. 字符映射

将字符 A、T、C 分别映射为 $0, 1, 2$，便于数组索引。

2. 前缀和计算

使用 $1$-based 索引简化边界处理，查询时注意区间端点转换为 $1$-based。

3. 公式计算

注意检查三个等式条件，以及计算最少交换次数的公式。

4. 示例验证

对于样例输入：

• 查询 $[1,3]$：$AT=0, TA=1, AC=1, CA=0, TC=1, CT=0$
  检查条件：$0+1=1+0$，$1+1=0+0$（不成立），实际应返回 $-1$？
  但样例输出是 $2$。让我们重新计算：对于子串 TAC 和 CTA：
  • 位置1：a='T', b='C' -> TC
  • 位置2：a='A', b='T' -> AT
  • 位置3：a='C', b='A' -> CA 所以 $TC=1, AT=1, CA=1$，其他为0。 检查条件：
  1. AT+AC=1+0=1, TA+CA=0+1=1 ✓
  2. TA+TC=0+1=1, AT+CT=1+0=1 ✓
  3. CA+CT=1+0=1, AC+TC=0+1=1 ✓ 计算：pairs = min(AT,TA)+min(AC,CA)+min(TC,CT)=0+0+0=0 cycles = 2*|AT-TA|=2*1=2 总交换次数为2。

---

算法标签

• 哈希和哈希表
• 前缀和
• 组合计数
• 构造性算法

---

总结

本题通过巧妙的分类与计数，将看似复杂的交换距离计算转化为简单的数学公式。关键在于发现：

1. 可转换的充要条件是各字符出现次数相等。
2. 不匹配位置可分为六类，并通过直接配对和三元环调整解决。