P8521 [IOI 2021] 修改 DNA

**滥用本题评测将被封号** **由于技术限制，请不要使用 C++ 14 (GCC 9) 语言提交本题。** 这是一道交互题，你只需要实现代码中要求的函数。 你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数

Grace 是一名生物学家，在新加坡的一个生物信息学公司工作。她的一部分工作是分析不同有机体的 DNA 序列。DNA 序列是包含字符 A、T 和 C 的字符串。注意在本题中，DNA 序列不包含字符 G。 定义一次修改是把 DNA 序列中的两个元素交换位置的操作。例如，通过交换加粗的字符 A 和 C，一次修改可以把 A**C**T**A** 转化为 A**A**T**C**。 两个序列的修改距离是把一个序列转化为另一个序列所用的最少修改次数。如果不能通过修改把一个序列转化为另一个序列，那么这两个序列的修改距离为 $-1$。 Grace 正在分析两个 DNA 序列 $a$ 和 $b$，每个都由 n 个元素组成，下标从 $0$ 到 $n - 1$。你的任务是帮助 Grace 回答以下形式的 $q$ 个问题：子串 $a[x \ldots y]$ 和 $b[x \ldots y]$ 的修改距离是多少？这里，DNA 序列 $s$ 的子串 $s[x \ldots y]$ 定义为 $s$ 的下标从 $x$ 到 $y$（包括 x 和 y）的连续字符序列。也就是说，$s[x \ldots y]$ 是序列 $s[x] s[x + 1] \ldots s[y]$。

你要实现以下函数： ```cpp void init(string a, string b) ``` - $a, b$：长度为 $n$ 的字符串，表示两个待分析的 DNA 序列。 恰好调用此函数一次，且发生在任何对 `get_distance` 的调用之前。 ```cpp int get_distance(int x, int y) ``` - $x, y$：待分析的子串的开始和结束下标。 此函数应返回子串 $a[x \ldots y]$ 和 $b[x \ldots y]$ 的修改距离。 恰好调用此函数 $q$ 次。

无

对于所有数据： - $1 \le n, q \le 100 \, 000$ - $0 \le x \le y \le n - 1$ - $a$ 和 $b$ 的每个字符都是 A、T 和 C 之⼀ 子任务|分值|特殊限制 :-:|:-:|:-: $1$ |$21$|$y - x \le 2$ $2$ |$22$| $q \le 500$，$y - x \le 1000$，$a$ 和 $b$ 的每个字符是 A 或 T $3$ |$13$| $a$ 和 $b$ 的每个字符是 A 或 T $4$ |$28$| $q \le 500$，$y - x \le 1000$ $5$ |$16$| 没有额外的约束条件 ## 样例解释 如果评测程序调用 `get_distance(1, 3)`，那么该调用应返回 $a[1 \ldots 3]$ 和 $b[1 \ldots 3]$（也就是序列 TAC 和 CTA）之间的修改距离。通过 $2$ 次修改可以把 TAC 转化为 CTA：TAC $\to$ CAT，然后是 CAT $\to$ CTA。无法通过比 $2$ 次更少的修改完成该转化。 因此，该调用应返回 $2$。 如果评测程序调用 `get_distance(4, 5)`，那么该调用应返回序列 AT 和 TA 之间的修改距离。 通过一次修改可以把 AT 转化为 TA，而且显然至少需要一次。 因此，该调用应返回 $1$。 最后，如果评测程序调用 `get_distance(3, 5)`，由于无法通过修改将序列 CAT 转化为 ATA，因此该调用应返回 $-1$。