P5057 【[CQOI2006]简单题】

洛谷P5057[CQOI2006]简单题

差分
树状数组基本操作不说了，主要想记录一下异或下的差分
a数组为每一位的真实值（假设(a[0]=0)），t为差分后的数组
则(t[i]=a[i])^(a[i-1])
所以我们如果想要查询(a[i])
则(a[i]=a[0])^$a[1]$(a[1])^$a[2]$(a[2])^$dots$(a[i])^{$a[i]$=$t[1]$}(t[2])^$dots$(t[i])
所以在树状数组中记录t数组，修改时指修改（异或上1）(l)和(r+1)的值就行
查询就是异或和
当然这个题的数据范围也可以分块做

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define R register
#define EN std::puts("")
#define LL long long
inline int read(){
	int x=0,y=1;
	char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return y?x:-x;
}
int n;
inline int lowbit(int x){return x&(-x);}
int tree[100006];
inline int fq(int pos){
	R int ans=0;
	for(;pos;pos-=lowbit(pos)) ans^=tree[pos];
	return ans;
}
inline void add(int pos){
	for(;pos<=n;pos+=lowbit(pos)) tree[pos]^=1;
}
int main(){
	n=read();int m=read();
	while(m--){
		int op=read();
		if(op==1){
			int l=read(),r=read();
			add(l);add(r+1);
		}
		else std::printf("%d
",fq(read()));
	}
	return 0;
}