题意：
有一字符串只包含0和1，然后又m组操作，I L R是将从L到R的字符进行翻转操作0变为1、1变为0，Q x表示询问第x的字符。
思路：
我们只需要计算对询问的字符进行了多少次翻转，如果是偶数次，该字符变，否则翻转。对于区间的更新，我们可以使用线段树，不过对于这个题，因为只是对点的查询，而且每个节点的初始值都相同，为0，因此我们可以直接使用树状数组。下面是一个很巧妙的做法，而且很容易理解。
用了树状数组的区间更新 单点查找（一般为单点更新 区间查找）
例如 区间（2,4）加1
则Updata(2,1) Updata(4+1,-1)
实现了更新（2,4）的值而不改变其他值
求Sum时即可得到某一点的值
//LA 1080 - Binary Simulation //2013-04-12-18.52 #include <stdio.h> #include <string.h> const int maxn = 100010; char str[maxn]; int n; int sum[maxn]; int lowbit(int x) { return x&(-x); } void change(int x, int v) { while (x <= n) { sum[x] += v; x += lowbit(x); } } int get(int x) { int s = 0; while (x) { s += sum[x]; x -= lowbit(x); } return s; } void update(int l, int r) { change(l, 1); change(r+1, -1); } int main() { int t, m; scanf("%d",&t); for(int i = 1; i <= t; i++) { memset(sum, 0, sizeof(sum)); scanf("%s",&str[1]); scanf("%d",&m); n =strlen(&str[1]); char op; int l, r; printf("Case %d:\n",i); while (m--) { getchar(); scanf("%c",&op); if (op == 'I') { scanf("%d %d",&l, &r); update(l, r); } else { scanf("%d",&l); if (get(l)%2 == 1) { if (str[l] == '1') puts("0"); else puts("1"); } else printf("%c\n",str[l]); } } } return 0; }
