题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1080
| Time Limit: 2 second(s) | Memory Limit: 64 MB |
Given a binary number, we are about to do some operations on the number. Two types of operations can be here.
'I i j' which means invert the bit from i to j (inclusive)
'Q i' answer whether the ith bit is 0 or 1
The MSB (most significant bit) is the first bit (i.e. i=1). The binary number can contain leading zeroes.
Input
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with a line containing a binary integer having length n (1 ≤ n ≤ 105). The next line will contain an integer q (1 ≤ q ≤ 50000) denoting the number of queries. Each query will be either in the form 'I i j'where i, j are integers and 1 ≤ i ≤ j ≤ n. Or the query will be in the form 'Q i' where i is an integer and 1 ≤ i ≤ n.
Output
For each case, print the case number in a single line. Then for each query 'Q i' you have to print 1 or 0 depending on the ith bit.
Sample Input |
Output for Sample Input |
|
2 0011001100 6 I 1 10 I 2 7 Q 2 Q 1 Q 7 Q 5 1011110111 6 I 1 10 I 2 7 Q 2 Q 1 Q 7 Q 5 |
Case 1: 0 1 1 0 Case 2: 0 0 0 1 |
Note
Dataset is huge, use faster i/o methods.
题目大意：给你一段二进制数，当输入为 I x y时。就把这段变成它的反串 。当为Q 就查询当前x这个位置的数字视为0还是1。
思路：此题有两种解题的思路，一种是线段树。一种是树状数组。当用树状数组时。能够看成是一个区间改动，单点查询的问题，当我们用线段树时。那么就须要用到懒惰标记。
对于这道题树状数组确实比线段是快非常多。
。。。
线段树代码：
//time 584 ms
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define L(u) u<<1
#define R(u) u<<1|1
using namespace std;
const int Max=100010;
char str[Max];
class Node
{
public:
int l,r;
char str;
int add;
}node[Max*4];
void build(int l,int r,int u)
{
node[u].l=l;
node[u].r=r;
node[u].add=0;
if(l==r)
{
node[u].str=str[l];
return;
}
int mid=(l+r)/2;
build(l,mid,L(u));
build(mid+1,r,R(u));
}
void pushdown(int u) //注意这儿要懒惰标记
{
node[L(u)].add+=node[u].add; //主义要加上。。。。
。
node[R(u)].add+=node[u].add;
node[u].add=0;
}
void update(int l,int r,int u)
{
if(l<=node[u].l&&node[u].r<=r)
{
node[u].add++;
return ;
}
if(node[u].add) pushdown(u);
int mid=(node[u].l+node[u].r)/2;
if(r<=mid)
{
update(l,r,L(u));
}
else if(l>mid)
{
update(l,r,R(u));
}
else
{
update(l,mid,L(u));
update(mid+1,r,R(u));
}
return ;
}
char query(int l,int r,int u)
{
if(l<=node[u].l&&node[u].r<=r)
{
if((node[u].add%2)==1)
{
node[u].add=0;
if(node[u].str=='1')
{
node[u].str='0';
return node[u].str;
}
else
{
node[u].str='1';
return node[u].str;
}
}
else
{
node[u].add=0;
return node[u].str;
}
}
if(node[u].add) pushdown(u);
int mid=(node[u].l+node[u].r)/2;
if(r<=mid)
{
return query(l,r,L(u));
}
else if(l>mid)
{
return query(l,r,R(u));
}
}
int main()
{
int T,q,i,j,kk=0;;
scanf("%d",&T);
while(T--)
{
getchar();
kk++;
str[0]='3';
scanf("%s",str+1);
int len=strlen(str);
build(1,len-1,1);
scanf("%d",&q);
char ch[5];
printf("Case %d:
",kk);
for(i=0;i<q;i++)
{
scanf("%s",ch);
if(ch[0]=='I')
{
int x,y;
scanf("%d%d",&x,&y);
update(x,y,1);
}
else
{
int x;
scanf("%d",&x);
printf("%c
",query(x,x,1));
}
}
}
return 0;
}
树状数组代码：
//time 304 ms
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
const int Max=100010;
int a[Max];
int n;
int lowbit(int x)
{
return x&(-x);
}
void insert(int x,int d)
{
while(x<=n)
{
a[x]+=d;
x+=lowbit(x);
}
}
int query(int x)
{
int res=0;
while(x>0)
{
res+=a[x];
x-=lowbit(x);
}
return res;
}
int main()
{
char str[Max],ch[5];
int T,q,kk=0;
scanf("%d",&T);
while(T--)
{
kk++;
memset(a,0,sizeof(a));
str[0]='2';
scanf("%s",str+1);
n=strlen(str)-1;
scanf("%d",&q);
printf("Case %d:
",kk);
for(int i=0;i<q;i++)
{
scanf("%s",ch);
if(ch[0]=='I')
{
int x,y;
scanf("%d%d",&x,&y);
insert(x,1);
insert(y+1,-1);
}
else
{
int x;
scanf("%d",&x);
int t=query(x);
if(t%2==1)
{
if(str[x]=='1')
{
printf("0
");
}
else
{
printf("1
");
}
}
else
{
printf("%c
",str[x]);
}
}
}
}
return 0;
}