洛谷 P5057 [CQOI2006]简单题（树状数组）

 1 #include<cstdio>
 2 #include<iostream>
 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             

#include<cstdio>
#include<iostream>

using namespace std;

int n, t[1000005];

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

inline 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;
}