零一奇迹（预处理+二进制构造+思维）

柔情只为你懂 2022-09-10 08:17 108阅读 0赞

一个长度为 n 的01字符串，有多少子串满足，其所表示的二进制数，对应的十进制数值在 l 和 r 之间（只统计不含前导零），取的位置可以决定不同。

询问的时间复杂度是1e4， 字符长度是1e5，不能每次都暴力查找。

因为每次修改的位置只有一个，遇到多次询问的问题，可以预处理，然后每次O(1) 时间复杂度去询问。

因为每次修改的范围大不，所以询问之前的修改，也是可以接受的。

每次修改：cul( (max(1, x - 63) ), x ) 把修改的范围缩小（这道题的灵魂之处）

先统计要修改的位置，然后修改，再统计修改的变化，拿总的和修改前后比较得出本次询问答案。

我感觉统计的时候也很妙，总是没见过就是很妙。

还是代佬大码：

#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;
    }