CF1196D2 RGB Substring (hard version)

本题的简单版与困难版唯一的区别在于输入规模的不同。 给定一个长度为 $n$ 的字符串 $s$，其中每个字符都是 'R'、'G' 或 'B'。 同时给定一个整数 $k$。你的任务是将初始字符串 $s$ 中的最少字符进行修改，使得修改后，$s$ 中存在一个长度为 $k$ 的子串，该子串同时也是无限字符串 "RGBRGBRGB..." 的一个子串。 如果存在正整数 $i$，使得 $a_1 = b_i$，$a_2 = b_{i+1}$，$a_3 = b_{i+2}$，...，$a_{|a|} = b_{i+|a|-1}$，则称字符串 $a$ 是字符串 $b$ 的一个子串。例如，字符串 "GBRG"、"B"、"BR" 都是无限字符串 "RGBRGBRGB..." 的子串，而 "GR"、"RGR" 和 "GGG" 不是。 你需要回答 $q$ 个独立的询问。

第一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示询问的数量。接下来有 $q$ 个询问。 每个询问的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$），分别表示字符串 $s$ 的长度和子串的长度。 每个询问的第二行包含一个长度为 $n$ 的字符串 $s$，仅由 'R'、'G'、'B' 组成。 保证所有询问中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

对于每个询问，输出一个整数，表示你需要修改的最少字符数，使得修改后 $s$ 中存在一个长度为 $k$ 的子串，同时也是无限字符串 "RGBRGBRGB..." 的子串。

在第一个样例中，你可以将第一个字符改为 'R'，得到子串 "RG"；或者将第二个字符改为 'R'，得到 "BR"；或者将第三、第四或第五个字符改为 'B'，得到 "GB"。 在第二个样例中，子串为 "BRG"。 由 ChatGPT 4.1 翻译