#P5057. [CQOI2006] 简单题

    ID: 3985 远端评测题 1000ms 500MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>树状数组线段树各省省选2006重庆

[CQOI2006] 简单题

题目描述

有一个 nn 个元素的数组,每个元素初始均为 00。有 mm 条指令,每条指令为两种操作中的一种:

  1. 让其中一段连续序列数字反转;(即 00111100
  2. 询问某个元素的值。

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

输入格式

第一行包含两个整数 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\% 的数据,1n1031 \le n \le 10^31m1041 \le m \le 10^4

对于 100%100\% 的数据,1n1051 \le n \le 10^51m5×1051 \le m \le 5 \times 10^5,保证 LRL \le R