CF1196D2.RGB Substring (hard version)

The only difference between easy and hard versions is the size of the input.

You are given a string $s$ consisting of $n$ characters, each character is 'R', 'G' or 'B'.

You are also given an integer $k$. Your task is to change the minimum number of characters in the initial string $s$ so that after the changes there will be a string of length $k$ that is a substring of $s$, and is also a substring of the infinite string "RGBRGBRGB ...".

A string $a$ is a substring of string $b$ if there exists a positive integer $i$ such that $a_1 = b_i$, $a_2 = b_{i + 1}$, $a_3 = b_{i + 2}$, ..., $a_{|a|} = b_{i + |a| - 1}$. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

You have to answer $q$ independent queries.

简单版本与困难版本的唯一区别在于输入规模。

给你一个由 $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$ 个相互独立的查询。

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries. Then $q$ queries follow.

The first line of the query contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the string $s$ and the length of the substring.

The second line of the query contains a string $s$ consisting of $n$ characters 'R', 'G' and 'B'.

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).

输入的第一行包含一个整数 $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$）。

For each query print one integer — the minimum number of characters you need to change in the initial string $s$ so that after changing there will be a substring of length $k$ in $s$ that is also a substring of the infinite string "RGBRGBRGB ...".

对于每个查询，输出一个整数——即需要修改初始字符串 $s$ 中的最少字符数，使得修改后字符串 $s$ 中存在一个长度为 $k$ 的子串，该子串同时也是无限字符串 “RGBRGBRGB...” 的子串。

In the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".

In the second example, the substring is "BRG".

在第一个例子中，你可以将第一个字符改为 'R'，从而得到子串 "RG"；或将第二个字符改为 'R'，从而得到 "BR"；或者将第三个、第四个或第五个字符改为 'B'，从而得到 "GB"。

在第二个例子中，子串为 "BRG"。