题解

这次挑战赛没时间打，挑了道最有趣的题目打。

看到这题我第一反应是线段树，先对每位异或 $i$ 的奇偶，就秒了。

但这样做太没意思了，所以考虑更简单的做法。

注意到区间反转不会改变区间内的不同，只会改变两端的不同。

所以考虑记录每个点是否不同，然后树状数组就行了。

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
class Fenwick_Tree{
	vector <int> tr;
	int n;
	public:
	
	Fenwick_Tree(){}
	Fenwick_Tree(int n){
		this -> n = n;
		tr.resize(n + 5);
	}
	void modify(int idx, int val){
		for(int i = idx; i <= n; i += (i & (-i))) tr[i] += val;
	}
	int query(int idx){
		int ans = 0;
		for(int i = idx; i; i -= (i & (-i))) ans += tr[i];
		return ans;
	}
};
string s;
int a[500005];
int n, m;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> s;
	s = ' ' + s;
	Fenwick_Tree tr(n + 5);
	for(int i = 1; i < n; i++){
		if(s[i] == s[i + 1]){
			tr.modify(i, 1);
			a[i] = 1;
		}
	}
	while(m--){
		int tmp, l, r;
		cin >> tmp >> l >> r;
		if(tmp == 1){
			if(l > 1){
				tr.modify(l - 1, a[l - 1] ? -1 : 1);
				a[l - 1] ^= 1;
			}
			if(r < n){
				tr.modify(r, a[r] ? -1 : 1);
				a[r] ^= 1;
			}
		}else{
			if(tr.query(r - 1) - tr.query(l - 1)) cout << "No\n";
			else cout << "Yes\n";
		}
	}

	return 0;
}