codeforces 1196D2 RGB Substring (hard version)

codeforces 1196D2 RGB Substring(hard version) 제목 링크
어려운 버전과 간단한 버전의 유일한 차이점은 데이터의 범위이다. 간단한 버전은 직접적으로 폭력을 행사할 수 있고 어려운 버전은 DP(동적 기획)가 필요하다.
제목:
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 a1=bi, a2=bi+1, a3=bi+2, …, a|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 q independent queries.
Input The first line of the input contains one integer q (1≤q≤2⋅105) — the number of queries. Then q queries follow.
The first line of the query contains two integers n and k (1≤k≤n≤2⋅105) — 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⋅105 (∑n≤2⋅105).
Output 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 …”.
샘플 입력:
3 5 2 BGGGG 5 3 RBRGR 5 5 BBBRR
출력 예제:
1 0 3
코드를 먼저 입력하십시오.

#include<bits/stdc++.h>
using namespace std;
int q,n,k;
string s;
char jh[3]={'R','G','B'};	//    
int f[200005];
int main(){
    cin>>q;
    for(int i=0;i<q;i++){
    	cin>>n>>k;
    	cin>>s;
    	int ans=300000;      //     ，   ans      ans
		for(int j=0;j<3;j++){   //           ，         
			int flag=j;			//    RGB   
			int cnt=0;
			for(int x=0;x<n;x++){	//  RGB         
				f[x]=(s[x]!=jh[flag]);	//           ，0   1  
				if(f[x]){
					cnt+=f[x];	//     
				}
				flag++;
				flag%=3;
				if(x>=k){	//  k     k+1 ，            
					cnt-=f[x-k];	//     ，         
				}
				if(x>=k-1){
					ans=min(ans,cnt);//   ans      ans
									 //      k-1 ,       k   
				}
			}
		}
    	cout<<ans<<endl;
	}
	return 0;
}

전체적인 사고방식:
우선, 우리의 사고방식은 n자 중에서 k 길이의 구간을 이동하고 변수 기록을 통해 최소치를 갱신하는 것이다. 물론 우리는 먼저 RGB의 순서를 확정해야 한다. RGBRGB일 수도 있고 GBRGBR일 수도 있다. 또는 BRGBRG일 수도 있다. 우리는 어느 것이 더 좋고 소모가 적은지 확정할 수 없다. 이 세 가지 가능한 순서를 수조로 우리가 매거하는 순서에 부합되는지 기록하고 이를 누적해야 한다. 길이가 k에 도달했을 때우리의 ans값을 계속 업데이트할 수 있습니다. 가장 작은 값을 취합니다. 물론 길이가 k+1일 때 가장 앞의 분의 소모를 줄여야 합니다. 구간이 전체적으로 이동하는 것과 유사하기 때문에 한 자리를 뒤로 가면 앞의 한 자리를 줄여야 합니다. 왜냐하면 제목은 연속 구간이 k인 RGB 순서에 부합되는 구간을 찾아야 하기 때문입니다. 정확하게 변경하는 데 필요한 최소 소모는 시간은 3*n이고 시간 복잡도는 O(n)밖에 없습니다.