题解 | 可匹配子段计数

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;

int t,n,m,k;
int a[N],b[N];
map<int,int> mp_b;

void solve(){
	
	map<int,int> mp_c;
	int res=0;
	
	for(int i=1;i<=m;i++){
		mp_c[a[i]]++;
	}
	
	int current_match=0;
	
	for(auto const& [v,countb]:mp_b){
		if(mp_c.count(v)!=0){
			current_match+=min(countb,mp_c[v]);
		}
	}
	
	if(current_match>=k){
		res++;
	}
	
	for(int i=2;i<=n-m+1;i++){
		int l=a[i-1],r=a[i+m-1];
		current_match=current_match-min(mp_c[l],mp_b[l]);
		current_match=current_match-min(mp_c[r],mp_b[r]);
		mp_c[l]--;mp_c[r]++;
		current_match=current_match+min(mp_c[l],mp_b[l]);
		current_match=current_match+min(mp_c[r],mp_b[r]);
		if(current_match>=k) res++;
	}
	cout<<res<<endl;
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>t;
	while(t--){
		mp_b.clear();
		cin>>n>>m>>k;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int j=1;j<=m;j++){
			cin>>b[j];
			mp_b[b[j]]++;
		} 
		solve();
	}

    return 0;
}