记录编号	596207	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO24 Open Gold]Cowreography	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.411 s
提交时间	2024-10-23 18:56:54	内存使用	13.38 MiB

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000010],b[1000010],x[1000010],y[1000010],nx[1000010],st=1,ny[1000010],st1=1;
int ctx,cty;
char l1[1000010],l2[1000010];
int main()
{
	freopen("cowreography.in","r",stdin);
    freopen("cowreography.out","w",stdout);
	scanf("%d%d",&n,&k);
	scanf("%s",l1+1);
	scanf("%s",l2+1);
	for(int i=1;i<=n;i++)
	{
		a[i]=l1[i]-'0';
		b[i]=l2[i]-'0';
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		while(nx[st]<i-k&&st<=ctx) st++;
		while(ny[st1]<i-k&&st1<=cty) st1++;   
		if(a[i]!=b[i])
		{
			if(a[i]==1)
			{
				y[i]++;                      
				ny[++cty]=i;                 
				if(st<=ctx)                  
				{
					x[nx[st]]--;
					y[i]--;
					cty--;
					if(x[nx[st]]<=0) st++;
					ans++;
				}
			}
			else
			{
				x[i]++;
				nx[++ctx]=i;
				if(st1<=cty)                
				{
					y[ny[st1]]--;
					x[i]--;
					ctx--;
					if(y[ny[st1]]<=0) st1++;
					ans++;
				}
			}
		}
		if(i-k>=1)
		{
			if(x[i-k]!=0)                  
			{
				ans+=x[i-k];
				x[i]+=x[i-k];
				if(nx[ctx]!=i) nx[++ctx]=i;
				x[i-k]=0;
			}
			if(y[i-k]!=0)                  
			{
				ans+=y[i-k];
				y[i]+=y[i-k];
				if(y[cty]!=i) ny[++cty]=i;
				y[i-k]=0;
			}
		}
	}
	printf("%lld",ans);
	return 0;
}