CF472G Design Tutorial: Increase the Constraints

有一种简单的方法可以创造出难题：将一个简单问题作为查询，并尝试找到一种比暴力更快的算法来解决它。这类问题通常出现在 OI 比赛中，且往往需要用到数据结构。 让我们以“Hamming 距离问题”为例进行出题：对于两个长度相同的二进制字符串 $s$ 和 $t$，它们的 Hamming 距离定义为对应位置上字符不同的个数。例如，"00111" 与 "10101" 的 Hamming 距离为 2（不同的位置已加粗标记）。 本题以 Hamming 距离作为查询：给定两个字符串 $a$ 与 $b$，以及若干查询。每个查询形式为：求 $a_{p1} a_{p1+1} \dots a_{p1+len-1}$ 和 $b_{p2} b_{p2+1} \dots b_{p2+len-1}$ 这两个子串的 Hamming 距离。 注意：本题字符串下标均从 $0$ 开始，即 $s = s_0 s_1 \dots s_{|s|-1}$。

第一行包含一个字符串 $a$（$1 \leq |a| \leq 200000$）。 第二行包含一个字符串 $b$（$1 \leq |b| \leq 200000$）。 第三行包含一个整数 $q$（$1 \leq q \leq 400000$），表示查询的数量。 接下来的 $q$ 行，每行包含三个整数 $p1$、$p2$ 和 $len$（$0 \leq p1 \leq |a| - len$；$0 \leq p2 \leq |b| - len$），表示当前查询的参数。

输出 $q$ 个整数，分别表示每个查询的答案。

由 ChatGPT 5 翻译