首页 > 代码库 > Light OJ 1080 - Binary Simulation - （线段树区间更新 单点查询）
Light OJ 1080 - Binary Simulation - （线段树区间更新 单点查询）
Description
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 fromi 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 lengthn(1 ≤ n ≤ 105). The next line will contain an integerq (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
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
Sample Output
Case 1:
0
1
1
0
Case 2:
0
0
0
1
题意：一串01序列，两种操作，一种是从i到j取反，一种是问第i个是0还是1.
把需要翻转的区间标记，记录这个区间的翻转次数，然后向下传标记，查询时只需看看这个点翻转奇数次还是偶数次。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <ctype.h>
#include <iostream>
#define lson o << 1, l, m
#define rson o << 1|1, m+1, r
using namespace std;
typedef long long LL;
const int MAX = 0x3f3f3f3f;
const int maxn = 111111;
int n, q, t, a, b, ans;
int cnt[maxn<<2];
char s[maxn], op[3];
void down(int o) {
if(cnt[o]) {
cnt[o<<1] += cnt[o];
cnt[o<<1|1] += cnt[o];
cnt[o] = 0;
}
}
void update(int o, int l, int r) {
if(a <= l && r <= b) {
cnt[o] ++;
return ;
}
down(o);
int m = (l+r) >> 1;
if(a <= m) update(lson);
if(m < b ) update(rson);
}
void query(int o, int l, int r) {
if(l == r) {
ans = s[l]-'0';
if(cnt[o]%2) ans = !ans;
return ;
}
down(o);
int m = (l+r) >> 1;
if(a <= m) query(lson);
else query(rson);
}
int main()
{
cin >> t; for(int ca=1;ca<=t;ca++) {
scanf("%s", s+1);
n = strlen(s+1);
memset(cnt, 0, sizeof(cnt));
printf("Case %d:\n", ca);
scanf("%d", &q); while(q--) {
scanf("%s", op);
if(op[0] == 'I') {
scanf("%d%d", &a, &b);
update(1, 1, n);
} else {
scanf("%d", &a);
query(1, 1, n);
printf("%d\n", ans);
}
}
}
return 0;
}