306434: CF1196D2. RGB Substring (hard version)
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
RGB Substring (hard version)
题意翻译
PS:此题目与类似的[CF1196D1](https://www.luogu.org/problem/CF1196D1)唯一的不同之处在于数据的范围。 给你$q$组询问($1 \le q \le 200000$) 每组询问会先给你一个$n$和一个$k$($1 \le k \le n \le 200000$) 下一行是一个字符串$s$(数据保证$s$只由大写字母$R$、$G$、$B$组成,输入数据保证所有$s$的长度和$ \le 200000$) 现在问你最少修改多少次$s$中的字母(一次只能修改一个字母),才能使得$s$的某一个子串是字符串$RGBRGBRGB...$的子串,同时该子串的长度$ \ge k$。题目描述
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.输入输出格式
输入格式
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 $ ).
输出格式
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 ...".
输入输出样例
输入样例 #1
3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR
输出样例 #1
1
0
3