好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

题目描述

题目来源：CQOI 2006

有一个 $n$ 个元素的数组，每个元素初始均为 $0$。有 $m$ 条指令，指令分为两种：

1. 操作 $1$：给定 $L, R$，将区间 $[L,R]$ 的每个数反转（$0$ 变 $1$，$1$ 变 $0$）；
2. 操作 $2$：给定 $i$，询问第 $i$ 个元素的值（输出 $0$ 或 $1$）。

请按顺序处理所有指令，并对每个操作 $2$ 输出一行答案。

输入格式

第一行包含两个整数 $n, m$，表示数组的长度和指令的条数。

接下来 $m$ 行，每行描述一个操作：

• 若第一个数为 $1$，则接下来有两个整数 $L, R$，表示区间反转操作；
• 若第一个数为 $2$，则接下来有一个整数 $i$，表示询问操作。

输出格式

对于每个操作 $2$，输出一行一个整数（$0$ 或 $1$），表示该位置的值。

样例

样例输入

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

样例说明

（原题中有详细的操作后数组变化表，这里用文字说明）

初始数组：$[0,0,\dots,0]$（长度 20）

1. 操作 1：反转 $[1,10]$ → 前 10 个变为 1，其余为 0；
2. 操作 2：问第 6 个值 → 1；
3. 操作 3：问第 12 个值 → 0；
4. 操作 4：反转 $[5,12]$ → 位置 5~10 从 1 变 0，位置 11~12 从 0 变 1；
   • 此时前 12 个：1,1,1,1,0,0,0,0,0,0,1,1
5. 操作 5：问第 6 个值 → 0；
6. 操作 6：问第 15 个值 → 0；
7. 操作 7：反转 $[6,16]$ → 变化较多；
8. 操作 8：反转 $[11,17]$；
9. 操作 9：问第 12 个值 → 0；
10. 操作 10：问第 6 个值 → 1。

数据范围

• 对于 $50\%$ 的数据，$1 \le n \le 10^3, 1 \le m \le 10^4$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^5, 1 \le m \le 5\times 10^5$，保证 $L \le R$。

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$（512 MB）

提示
此题为 区间修改（异或 1）、单点查询 问题。

由于反转操作可以看作对区间内每个数加 1 再模 2（即异或 1），我们需要一个数据结构支持：

• 区间加 1（模 2 意义下）；
• 单点查询（模 2 后的值）。

方法一：树状数组（差分思想）
将原数组 $a$ 的差分数组 $d$ 定义为 $d[i] = a[i] \oplus a[i-1]$（$\oplus$ 表示异或），则：

• 区间 $[L,R]$ 反转：$d[L] \oplus= 1, d[R+1] \oplus= 1$；
• 单点查询 $a[i]$：$a[i] = d[1] \oplus d[2] \oplus \dots \oplus d[i]$。

这样就将区间修改转化为两个单点修改（异或 1），单点查询转化为前缀异或和查询。
可以用树状数组维护 $d$ 数组的前缀异或和（因为异或运算满足结合律和交换律，树状数组可以维护）。

方法二：线段树
直接维护区间和，反转操作相当于区间值取反（$sum \to len - sum$），同时打懒标记。单点查询时递归到叶子节点返回。

由于 $n, m$ 较大，树状数组常数更小，推荐使用方法一。

树状数组实现步骤：

1. 初始化树状数组 $tree$ 全为 $0$；
2. 对于操作 1（$L, R$）：
   • add(L, 1)（即 $d[L] \oplus 1$）；
   • add(R+1, 1)（注意 $R+1 \le n+1$）；
3. 对于操作 2（$i$）：
   • 输出 sum(i) % 2（即前缀异或和模 2，但树状数组维护的是异或和，直接 sum(i) & 1 即可）。

复杂度：每次操作 $O(\log n)$。

注意：

• 异或操作在树状数组中仍可用加法实现，因为模 2 加法等价于异或；
• 树状数组的 add 操作将对应位置的值加 1（模 2），sum 操作返回前缀和模 2 的结果。