pypy3 解法, 执行用时: 2761ms, 内存消耗: 78312K, 提交时间: 2023-01-03 21:04:18

n,m,len=map(int,input().split())
li=list(map(int,input().split()))+[range(n+6)]
ans=0
for i in range(n-len-1):
    if li[i]==0 or li[i+len+1]==0:
        ans+=1
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    if li[a]==b:
        pass
    if li[a]==0:
        if a>=len+1 and li[a-len-1]!=0:
            ans-=1
        if a+len+1<n and li[a+len+1]!=0:
            ans-=1
    if b!=0:
        pass
    else:
        if a>=len+1 and li[a-len-1]!=0:
            ans+=1
        if a+len+1<n and li[len+a+1]!=0:
            ans+=1
    li[a]=b
    print(ans)

C++(g++ 7.5.0) 解法, 执行用时: 276ms, 内存消耗: 7816K, 提交时间: 2022-12-31 09:39:43

#include<bits/stdc++.h>
#define N 500010
using namespace std;
int n,m,k,ans;
long long a[N];

void go(int p,int v){
	if (p-k-1>0 && a[p-k-1]*a[p]==0) ans--;
	if (p+k+1<=n && a[p+k+1]*a[p]==0) ans--;
	a[p]=v;
	if (p-k-1>0 && a[p-k-1]*a[p]==0) ans++;
	if (p+k+1<=n && a[p+k+1]*a[p]==0) ans++;

}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m>>k;
	memset(a,-1,sizeof a);
	for(int i=1;i<=n;i++) {
		int x;
		cin>>x;
		go(i, x);
	}
	while(m--){
		int p, v;
		cin>>p>>v;
		go(p, v);
		cout<<ans<<'\n';
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 1726ms, 内存消耗: 14972K, 提交时间: 2022-12-31 23:39:53

#include<bits/stdc++.h>
using namespace std;
int a[500500],b[500500];
int main()
{
	int n,m,len,sum=0;
	cin>>n>>m>>len;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=len+2;i<=n;i++)
	{
		if(a[i]==0||a[i-len-1]==0) sum++;
	}
	while(m--)
	{
		
		int x,y,k;
		cin>>x>>y;
		k=a[x];
		a[x]=y;
		if(k==0&&y!=0) 
		{
			if(x>=len+2&&a[x-len-1]!=0) sum--;
			if(x<=n-len-1&&a[x+len+1]!=0) sum--;
		}
		else if(k!=0&&y==0)
		{
			if(x>=len+2&&a[x-len-1]!=0) sum++;
			if(x<=n-len-1&&a[x+len+1]!=0) sum++;
		}
		cout<<sum<<endl;
	}
}