题目链接: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; }
I read this article completely concerning the comparison of hottest and previous technologies, it’s remarkable
article.