#422. 树状数组-简单题

树状数组-简单题

题目描述

题目来源:CQOI 2006

有一个 nn 个元素的数组,每个元素初始均为 00。有 mm 条指令,要么让其中一段连续序列数字反转——00111100(操作 11),要么询问某个元素的值(操作 22)。

例如当 n=20n=20 时,1010 条指令如下:

操作 回答 操作后的数组
1 1 101\ 1\ 10 N/A 1111111111000000000011111111110000000000
2 62\ 6 11 1111111111000000000011111\underline{1}11110000000000
2 122\ 12 00 1111111111000000000011111111110\underline{0}00000000
1 5 121\ 5\ 12 N/A 1111000000110000000011110000001100000000
2 62\ 6 00 1111000000110000000011110\underline{0}00001100000000
2 152\ 15 1111000000110000000011110000001100\underline 000000
1 6 161\ 6\ 16 N/A 11110111110011110000 11110111110011110000
1 11 171\ 11\ 17 1111011111110000100011110111111100001000
2 122\ 12 11 1111011111110000100011110111111\underline 100001000
2 62\ 6 1111011111110000100011110\underline 111111100001000

输入格式

第一行包含两个整数 n,mn,m,表示数组的长度和指令的条数;
以下 mm 行,每行的第一个数 tt 表示操作的种类:

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

输出格式

每个操作 22 输出一行(非 0011),表示每次操作 22 的回答。

样例

样例输入

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\% 的数据,1n103,1m1041\le n\le 10^3,1\le m\le 10^4
对于 100%100\% 的数据,1n105,1m5×1051\le n\le 10^5,1\le m\le 5\times 10^5,保证 LRL\le R