题解"/>
洛谷P5057 [CQOI2006]简单题题解
[CQOI2006]简单题
洛谷P5057 [CQOI2006]简单题
题目描述
有一个 n 个元素的数组,每个元素初始均为 0。有 m 条指令,要么让其中一段连续序列数字反转——0 变 1,1 变 0(操作 1),要么询问某个元素的值(操作 2)。 例如当 n = 20 时,10 条指令如下:
输入输出格式
输入格式:
第一行包含两个整数 n, m,表示数组的长度和指令的条数; 以下 m 行,每行的第一个数 t 表示操作的种类:
若 t = 1,则接下来有两个数 L, R,表示区间 [L, R] 的每个数均反转; 若 t = 2,则接下来只有一个数 i,表示询问的下标。
输出格式:
每个操作 2 输出一行(非 0 即 1),表示每次操作 2 的回答。
输入输出样例
输入样例
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
输出样例
1
0
0
0
1
1
说明
对于 50% 的数据,1 ≤ n ≤ 10^3 , 1 ≤ m ≤ 10^4 ; 对于 100% 的数据,1 ≤ n ≤ 10^5 , 1 ≤ m ≤ 5 × 10^5 ,保证 L ≤ R。
看大家用的都是树状数组,赶紧来一发线段树。
思路:简单线段树,只要把区间加改成区间xor即可。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int t[400010];//如果t[i]不为叶子节点,t[i]为标记,否则t[i]为数值
void down(int k)
{if(t[k]){t[k<<1]^=1;t[k<<1|1]^=1;t[k]=0;}
}
void change(int k,int l,int r,int x,int y)
{if(x<=l&&r<=y)//如果当前区间完全被修改区间包含,整体xor{t[k]^=1;return;}down(k);//下传标记int mid=(l+r)>>1;if(x<=mid)change(k<<1,l,mid,x,y);if(mid<y)change(k<<1|1,mid+1,r,x,y);
}
int ask(int k,int l,int r,int x)
{if(l==r)return t[k];down(k);//下传标记int mid=(l+r)>>1;if(x<=mid)return ask(k<<1,l,mid,x);else return ask(k<<1|1,mid+1,r,x);
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int k,x,y;scanf("%d%d",&k,&x);if(k==1){scanf("%d",&y);change(1,1,n,x,y);}elseprintf("%d\n",ask(1,1,n,x));}return 0;
}
更多推荐
洛谷P5057 [CQOI2006]简单题题解
发布评论