题目链接：LibreOJ 10117/Luogu P5057/信息学奥赛一本通 T1539

题目

题目描述

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

输入格式

第一行包含两个整数 n,m，表示数组的长度和指令的条数；
以下 m 行，每行的第一个数 t 表示操作的种类：
若 t=1，则接下来有两个数 L,R，表示区间 [L,R] 的每个数均反转；
若 t=2，则接下来只有一个数 i，表示询问的下标。

输出格式

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

样例输入输出

#1

• Input:

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

• Output:

1
1
1

题解

思路

差分+树状数组。
这道题比较简单，但是要注意细节：

差分数组不能出现零下标。

代码

代码比较简单。
算法的时间复杂度为 $\Theta(n\log _ 2n)$。

#include
//以上为头文件
const int MAXN=100000+5;//N的最大数据范围
const int MAXM=500000+5;//M的最大数据范围
struct TreeArray{//树状数组模板
    #define lowbit(x) ( (x) & ( - (x) ) ) //宏定义
    int n,unit[MAXN];
    void Update(int ID,int val){
        while(ID<=n){
            unit[ID]+=val;
            ID+=lowbit(ID);
        }
        return;
    }
    int Query(int ID){
        register int sum=0;
        while(ID){
            sum+=unit[ID];
            ID-=lowbit(ID);
        }
        return sum;
    }
    #undef lowbit
};
int n,m;
TreeArray T;
int main(void){
    register int i;
    scanf("%d%d",&n,&m);
    T.n=n+1;//注意细节
    for(i=1;i<=m;++i){
        static int t,l,r,x;
        scanf("%d",&t);
        if(t==1){
            scanf("%d%d",&l,&r);
            T.Update(l,1);//注意细节
            T.Update(r+1,-1);//注意细节
        }
        if(t==2){
            scanf("%d",&x);
            printf("%d\n",T.Query(x)&1);//注意细节
        }
    }
    return 0;
}