简单题(easy)

Description

有一个 n个元素的数组，每个元素初始均为 0。有 m条指令，要么让其中一段连续序列数字反转—— 0变 1，1变 0（操作 1），要么询问某个元素的值（操作 2）。

例如当 n = 20时，10条指令如下：

image.png

Input

第一行包含两个整数 n,m，表示数组的长度和指令的条数；
以下 m行，每行的第一个数 t表示操作的种类：

  • 若 t = 1，则接下来有两个数 L, R，表示区间 [L, R]的每个数均反转；
  • 若 t = 2，则接下来只有一个数 i，表示询问的下标。

Output

每个操作 2输出一行（非 0即 1），表示每次操作 2的回答。

Sample Input 1 

20 10
1 1 10
2 6
2 12
1 5 12
2 6
2 15
1 6 16
1 11 17
2 12
2 6

Sample Output 1

1
0
0
0
1
1

Hint

对于 50%的数据，1 <= n <= 10^3, 1 <= m <= 10^4；

对于 100%的数据，1 <= n <= 10^5, 1 <= m <= 5*10^5，保证 L <= R。

题解：

树状数组+差分

区间修改+单点查询

刚接触树状数组，感觉有点难想，对于给出的边界[l,r]，维护差分数组，对从l到n的位置进行+1操作，然后对r+1到n的位置进行-1操作，这样就不需要再做差了，这样得出的值便是单点查询的值，而不是原来的区间查询，然后用得到的sum去模2，看反转的次数，sum%2得到的结果就是最后的答案

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e5+5;
int c[maxn],sum[maxn];
int n,m;

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

int getsum(int x){
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

void update(int x,int v){
    while(x <= n){
        c[x] += v;
        x += lowbit(x);
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0 ; i < m ; i++){
        int t;
        cin >> t;
        if(t == 1){
            int l,r;
            cin >> l >> r;
            update(l,1),update(r+1,-1);
        }else if(t == 2){
            int k;
            cin >> k;
            cout << getsum(k)%2 << endl;
        }
    }
    return 0;
}