嗯...
题目链接：https://www.luogu.org/problem/P5057
首先发现这道题中只有0和1，所以肯定与二进制有关。然后发现这道题需要支持区间更改和单点查询操作，所以首先想到的是异或意义下的差分数组，于是自己便写了一个差分数组，确实好写，但很慢（可能我写的不优），下面是五十分的异或意义下的差分的代码：
1 #include2 #include 3 4 using namespace std; 5 6 int a[100005], b[100005]; 7 8 int main(){ 9 int n, m, t, l, r, x;10 scanf("%d%d", &n, &m);11 for(int i = 1; i <= n; i++) b[i] = a[i] ^ a[i - 1];12 for(int i = 1; i <= m; i++){13 scanf("%d", &t);14 if(t == 1){15 scanf("%d%d", &l, &r);16 b[l] ^= 1;17 b[r + 1] ^= 1;18 for(int i = 1; i <= n; i++)19 a[i] = a[i - 1] ^ b[i]; 20 }21 else{22 scanf("%d", &x);23 printf("%d\n", a[x]);24 }25 }26 return 0;27 }28
很明显，我写的差分时间复杂度在O（mn）左右，所以超时...
而正解是用树状数组来维护，因为树状数组支持区间更改和单点查询。注意单点查询之后，也是本题最神奇的地方，将查询的10进制%2，即可得它的二进制的最后一位即为答案（也可以理解为进行奇数次操作会改变，进行偶数次操作不会改变）
AC代码：
#include#include using namespace std;int n, t[1000005];inline int lowbit(int x){ return x & -x;}//lowbitinline void change(int x, int k){ while(x <= n){ t[x] += k; x += lowbit(x); } return;}//区间更改inline int check(int x){ int ans = 0; while(x > 0){ ans += t[x]; x -= lowbit(x); } return ans;}//单点查询int main(){ int m, l, r, f, d; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++){ scanf("%d", &f); if(f == 1){ scanf("%d%d", &l, &r); change(l, 1); change(r + 1, -1); } else{ scanf("%d", &d); printf("%d\n", check(d) % 2);//核心 } } return 0;}