C++(g++ 7.5.0) 解法, 执行用时: 144ms, 内存消耗: 748K, 提交时间: 2023-05-01 21:37:07

#include<iostream>
using namespace std;
#define rep(i,l,r) for(int i = l; i <= r; i++)
#define fep(i,a,b) for(int i=b; i>=a; --i)
typedef long long ll;

string s;
ll n, l, r, q;

ll cul(int L, int R)
{
	ll ans = 0;
	rep(i,L,R)
	{
		if(s[i]=='0') continue;

		ll tmp = 0;

		for(int j=1;j<=64 and i+j-1<=n; j++)
		{
			int now = i + j - 1;
			tmp = (tmp<<1) + (s[now]-'0');
			if(tmp >= l and tmp <= r) ans++;
			if(tmp > r) break;
		}
	}
	return ans;
}

void solve()
{

	cin >> n >> l >> r >> s >> q;

	s=" "+s;

	ll ans=0;
	rep(i,1,q)
	{
		int x; cin >> x;

		ll t1 = cul(max(1, x-63), x);

		s[x] = (s[x] == '0') ? '1' : '0';

		ll t2 = cul(max(1, x-63), x);

		if(i==1) ans = cul(1, n);

		else ans += t2 - t1;

		cout << ans << endl;
	}
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	solve();
	return 0;
}

C++ 解法, 执行用时: 85ms, 内存消耗: 520K, 提交时间: 2021-08-08 11:17:15

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Min(x,y)((x)<(y)?x:y)
#define Max(x,y)((x)>(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
ll l,r;
int n,k;
char s[100005];
void calc(int i,int type)
{
	int j;
	ll t=0;
	For(j,i,Min(i+65,n))
	{
		t=t<<1|(s[j]-'0');
		if(t>r)break;
		k+=(t>=l)*type;
	}
}
int main()
{
	int q,i,a;
	scanf("%d%lld%lld%s%d",&n,&l,&r,s+1,&q);
	For(i,1,n)
	if(s[i]=='1')calc(i,1);
	while(q--)
	{
		scanf("%d",&a);
		For(i,Max(a-65,1),a)
		if(s[i]=='1')calc(i,-1);
		s[a]='1'-s[a]+'0';
		For(i,Max(a-65,1),a)
		if(s[i]=='1')calc(i,1);
		printf("%d\n",k);
	}
	return 0;
}