题目描述
题目来源：CQOI 2006
有一个
n
n 个元素的数组，每个元素初始均为
0
0。有
m
m 条指令，要么让其中一段连续序列数字反转——
0
0 变
1
1，
1
1 变
0
0（操作
1
1），要么询问某个元素的值（操作
2
2）。
例如当
n=20
n=20 时，
10
10 条指令如下：
操作 回答 操作后的数组
1\ 1\ 10
1 1 10 N/A
11111111110000000000
11111111110000000000
2\ 6
2 6
1
1
11111\underline{1}11110000000000
111111
11110000000000
2\ 12
2 12
0
0
11111111110\underline{0}00000000
111111111100
00000000
1\ 5\ 12
1 5 12 N/A
11110000001100000000
11110000001100000000
2\ 6
2 6
0
0
11110\underline{0}00001100000000
111100
00001100000000
2\ 15
2 15
0
0
11110000001100\underline 000000
111100000011000
00000
1\ 6\ 16
1 6 16 N/A
11110111110011110000
11110111110011110000
1\ 11\ 17
1 11 17 N/A
11110111111100001000
11110111111100001000
2\ 12
2 12
1
1
11110111111\underline 100001000
111101111111
00001000
2\ 6
2 6
1
1
11110\underline 111111100001000
111101
11111100001000
输入
第一行包含两个整数
n,m
n,m，表示数组的长度和指令的条数；
以下
m
m 行，每行的第一个数
t
t 表示操作的种类：
若
t=1
t=1，则接下来有两个数
L, R
L,R，表示区间
[L, R]
[L,R] 的每个数均反转；
若
t=2
t=2，则接下来只有一个数
i
i，表示询问的下标。
输出
每个操作
2
2 输出一行（非
0
0 即
1
1），表示每次操作
2
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\%
50% 的数据，
1\le n\le 10^3,1\le m\le 10^4
1≤n≤103,1≤m≤104；
对于
100\%
100% 的数据，
1\le n\le 10^5,1\le m\le 5\times 10^5
1≤n≤105,1≤m≤5×105，保证
L\le R
L≤R。
来源/分类
ybttg 树状数组