首页 > 代码库 > 1080 - Binary Simulation
1080 - Binary Simulation
| PDF (English) | Statistics | Forum |
| 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.
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<string.h> 5 #include<queue> 6 #include<math.h> 7 using namespace std; 8 char str[100005]; 9 int tree[4*100005];10 void in(int l,int r,int k,int nn,int mm)11 {12 if(l>mm||r<nn)13 {14 return ;15 }16 else if(l<=nn&&r>=mm)17 {18 tree[k]++;19 tree[k]%=2;20 return ;21 }22 else23 {24 tree[2*k+1]+=tree[k];25 tree[2*k+1]%=2;26 tree[2*k+2]+=tree[k];27 tree[2*k+2]%=2;28 tree[k] = 0;29 in(l,r,2*k+1,nn,(nn+mm)/2);30 in(l,r,2*k+2,(nn+mm)/2+1,mm);31 }32 }33 int ask(int l,int r,int k,int nn,int mm)34 {35 if(l>mm||r<nn)36 {37 return 0;38 }39 else if(l<=nn&&r>=mm)40 {41 return tree[k];42 }43 else44 {45 tree[2*k+1]+=tree[k];46 tree[2*k+1]%=2;47 tree[2*k+2]+=tree[k];48 tree[2*k+2]%=2;49 tree[k] = 0;50 int nx = ask(l,r,2*k+1,nn,(nn+mm)/2);51 int ny = ask(l,r,2*k+2,(nn+mm)/2+1,mm);52 return (nx + ny)%2;53 }54 }55 int main(void)56 {57 int T;58 scanf("%d",&T);59 int __ca = 0;60 while(T--)61 {62 __ca++;63 printf("Case %d:\n",__ca);64 memset(tree,0,sizeof(tree));65 scanf("%s",str);66 int n;int l = strlen(str);67 scanf("%d ",&n);68 while(n--)69 {70 char a[10];71 int x,y;72 scanf("%s",a);73 if(a[0] == ‘I‘)74 {scanf("%d %d",&x,&y);75 in(x-1,y-1,0,0,l-1);76 }77 else78 {79 int x;80 scanf("%d",&x);81 int ny = ask(x-1,x-1,0,0,l-1);82 printf("%d\n",(str[x-1]-‘0‘+ny)%2);83 }84 }85 }return 0;86 }
1080 - Binary Simulation