题意:
有一字符串只包含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;
}
这题也可以用线段树来做,个人感觉没有必要,有兴趣的读者可以试试。