Description

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

You are given a string ss consisting of nn characters, each character is ‘R‘, ‘G‘ or ‘B‘.

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

A string aa is a substring of string bb if there exists a positive integer ii such that a1=bia1=bi, a2=bi+1a2=bi+1, a3=bi+2a3=bi+2, ..., a|a|=bi+|a|−1a|a|=bi+|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 qq independent queries.

Input

The first line of the input contains one integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of queries. Then qq queries follow.

The first line of the query contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — the length of the string ss and the length of the substring.

The second line of the query contains a string ss consisting of nn characters ‘R‘, ‘G‘ and ‘B‘.

It is guaranteed that the sum of nn over all queries does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105).

output

Examples

正确解法：

给你一个长度为n的字串，让你修改几个字符，使他拥有一个　　“RGBRGBR...”长度为k的连续子字符串。

我们设三个长度为n的字符串：

RGBRGB...

GBRGBR...

BRGBRG...

分别匹配他与当前字符串的匹配度。

也就是说如果某个字符相等的话，匹配度+1。

最后找 长度为k的连续子字符串匹配度的最大值。

k-这个最大值，就是 修改的最小次数。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <cctype>
10 #include <sstream>
11 using namespace std;
12 typedef long long ll;
13 const int inf=0x7fffffff;
14 const int N=200000+100;
15 const int M=5000+10;
16 const double PI=acos(-1.0);
17 int T;
18 int n,k;
19 string s;
20 string k1="RGB",k2="GBR",k3="BRG";
21 int sum[5][N];
22 int main()
23 {
24     scanf("%d",&T);
25     while(T--)
26     {
27         scanf("%d %d",&n,&k);
28         cin>>s;
29         for(int i=0;i<=n+1;i++)
30             sum[0][i]=sum[1][i]=sum[2][i]=0;
31         for(int i=0;i<n;i++)
32         {
33             sum[0][i+1]=sum[0][i];
34             sum[1][i+1]=sum[1][i];
35             sum[2][i+1]=sum[2][i];
36             if(s[i]==k1[i%3])   sum[0][i+1]++;
37             if(s[i]==k2[i%3])   sum[1][i+1]++;
38             if(s[i]==k3[i%3])   sum[2][i+1]++;
39         }
40         int ans=0;
41         for(int i=0;i+k<=n;i++)
42             for(int j=0;j<3;j++)
43                 ans=max(ans,sum[j][i+k]-sum[j][i]);
44         printf("%d\n",k-ans);
45  
46     }
47  
48     return 0;
49 }

View Code

[CF]Codeforces Round #575 (Div. 3)

原文：https://www.cnblogs.com/Kaike/p/11250569.html