题解 | 区间取反与单点求值

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+10;

int n,q;
string s;
int c[N];

int lowbit(int x){
	return x&(-x);
}

void add(int i,int x){
	for(i;i<=n;i+=lowbit(i)){
		c[i]=(c[i]+x)%2;
	}
	return;
}

int query(int i){
	int res=0;
	for(i;i>=1;i-=lowbit(i)){
		res=(res+c[i])%2;
	}
	return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>q;
	cin>>s;
	int op,l,r,x;
	for(int i=1;i<=q;i++){
		cin>>op;
		if(op==1){
			cin>>l>>r;
			add(l,1);
			add(r+1,1);
		}else if(op==2){
			cin>>x;
			int cnt=query(x);
			int ans=(s[x-1]-'0')^cnt;
			cout<<ans<<endl;
		}
	}

    return 0;
}