#448. 简单题

简单题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

题目来源:CQOI 2006

有一个 n\red{n} 个元素的数组,每个元素初始均为 0\red{0}。有m\red{ m }条指令,要么让其中一段连续序列数字反转——0\red{0}1\red{1}1\red{1}0\red{ 0}(操作 1\red{1}),要么询问某个元素的值(操作 2\red{2})。

例如当 n=20\red{n=20 }时,10\red{10 }条指令如下:

操作 回答 操作后的数组
1 1 10\red{1\ 1\ 10 } N/A\red{N/A } 11111111110000000000\red{11111111110000000000 }
2 6\red{2\ 6 } 1\red{1 } 11111111110000000000\red{11111\underline{1}11110000000000}
2 12\red{2\ 12 } 0\red{0 } 11111111110000000000\red{11111111110\underline{0}00000000}
1 5 12\red{1\ 5\ 12 } N/A\red{N/A } 11110000001100000000\red{11110000001100000000 }
2 6\red{2\ 6 } 0\red{0 } 11110000001100000000\red{11110\underline{0}00001100000000}
2 15\red{2\ 15 } 11110000001100000000\red{11110000001100\underline 000000 }
1 6 16\red{1\ 6\ 16 } N/A\red{N/A } 11110111110011110000\red{11110111110011110000 }
1 11 17\red{1\ 11\ 17 } 11110111111100001000\red{11110111111100001000 }
2 12\red{2\ 12 } 1\red{1 } 11110111111100001000\red{11110111111\underline 100001000}
2 6\red{2\ 6 } 11110111111100001000\red{11110\underline 111111100001000}

输入格式

第一行包含两个整数 n,m\red{n,m},表示数组的长度和指令的条数; 以下m\red{ m} 行,每行的第一个数 t\red{t} 表示操作的种类:

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

输出格式

每个操作2\red{ 2} 输出一行(非 0\red{0}1\red{1}),表示每次操作2\red{ 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%\red{50\% }的数据,1n103,1m104\red{1\le n\le 10^3,1\le m\le 10^4}

对于 100%\red{100\% }的数据,1n105,1m5×105\red{1\le n\le 10^5,1\le m\le 5\times 10^5},保证 LR\red{L\le R}

数据结构2

未参加
状态
已结束
规则
IOI
题目
14
开始于
2023-1-8 16:00
结束于
2023-1-18 16:00
持续时间
240 小时
主持人
参赛人数
19