题目链接：https://www.luogu.com.cn/problem/P5057
题目中首先给出一个全零序列，操作有两种，一种是将[l,r]区间的01序列取反，还有一种是单点更新。我们考虑到取反可以让这个位与1求异或，可以用树状数组更新一段，异或运算和加法运算有着很相似的地方，对于加法，我们为了更新一段区间可以构造序列的拆分数列，维护拆分序列，这样的话就变成了的更新两个点，因为在区间中的拆分数列值只有端点会发生变化，中间的值不会发生变化。异或也是同样的计算。在此树状数组维护的是异或前缀和。
下面我来简单地证明该算法的正确性：
最后贴上树状数组的求解代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x3f3f3f3f 20 const int maxn=1e6+10; 21 int n,m,t; 22 inline int read(){ 23 int ans=0,w=1; 24 char ch=getchar(); 25 while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} 26 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); 27 return ans*w; 28 } 29 int lowbit(int x) 30 { 31 return x&(-x); 32 } 33 int c[maxn]; 34 int query(int x) 35 { 36 int ans=0; 37 for(int i=x;i;i-=lowbit(i))ans^=c[i]; 38 return ans; 39 } 40 void update(int x) 41 { 42 for(int i=x;i<=n;i+=lowbit(i)) 43 { 44 c[i]^=1; 45 } 46 } 47 int main() 48 { 49 //freopen("input.txt","r",stdin); 50 //freopen("output.txt","w",stdout); 51 std::ios::sync_with_stdio(false); 52 n=read(),m=read(); 53 int op; 54 int l,r; 55 f(i,1,m) 56 { 57 op=read(); 58 if(op==1) 59 { 60 l=read(); 61 r=read(); 62 update(l); 63 update(r+1); 64 } 65 if(op==2) 66 { 67 l=read(); 68 pf("%d ",query(l)); 69 } 70 } 71 }
根据翻转的性质，只可能是从0->1或者1->0，所以我们在一段区间上加上1之后对他取模将会得到与翻转一样的结果，由于加法运算和取模运算的可交换性质，我们在最终取模将会得到最终翻转的结果。所以这个题目就变成了一道区间加法加点查询的题目，树状数组维护原序列的拆分即可。代码如下：（线段树的话，非常地繁琐，就不贴了）
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x3f3f3f3f 20 const int maxn=1e6+10; 21 int n,m,t; 22 inline int read(){ 23 int ans=0,w=1; 24 char ch=getchar(); 25 while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} 26 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); 27 return ans*w; 28 } 29 int lowbit(int x) 30 { 31 return x&(-x); 32 } 33 int c[maxn]; 34 int query(int x) 35 { 36 int ans=0; 37 for(int i=x;i;i-=lowbit(i))ans+=c[i]; 38 return ans; 39 } 40 void update(int x,int y) 41 { 42 for(int i=x;i<=n;i+=lowbit(i)) 43 { 44 c[i]+=y; 45 } 46 } 47 int main() 48 { 49 //freopen("input.txt","r",stdin); 50 //freopen("output.txt","w",stdout); 51 std::ios::sync_with_stdio(false); 52 n=read(),m=read(); 53 int op; 54 int l,r; 55 f(i,1,m) 56 { 57 op=read(); 58 if(op==1) 59 { 60 l=read(); 61 r=read(); 62 update(l,1); 63 update(r+1,-1); 64 } 65 if(op==2) 66 { 67 l=read(); 68 pf("%d ",query(l)%2); 69 } 70 } 71 }