A - Binary Simulation

线段树

题目大意

给出一行字符串，只包含 0 和 1，给出操作选项；I： 为把一个区间内字符反向 0 变为 1，1 变为 0；Q：查询第 i 个字符。

解题思路

线段树模板题...区间更新反转次数，奇数次反转

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
using namespace std;
int const MAX = 1e5 + 5;
int chg[MAX << 2], lazy[MAX << 2];
char s[MAX];
int n, len;
void PushDown(int rt)
{
    if(lazy[rt])
    {
        chg[rt << 1] += lazy[rt];
        chg[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
    return;
}
void Update(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        chg[rt] ++;
        lazy[rt] ++;
        return;
    }
    int mid = (l + r) >> 1;
    PushDown(rt);
    if(L <= mid)
        Update(L, R, lson);
    if(mid < R)
        Update(L, R, rson);
}
int Query(int L, int R, int l, int r, int rt)
{
    if(L == l && r == R)
        return chg[rt];
    int mid = (l + r) >> 1, ans = 0;;
    PushDown(rt);
    if(L <= mid)
        return Query(L, R, lson);
    if(mid < R)
        return Query(L, R, rson);
    return ans;
}
int main()
{
    int T;
    scanf("%d", &T);
    for(int ca = 1; ca <= T; ca++)
    {
        scanf("%s %d", s + 1, &n);
        len = strlen(s + 1);
        memset(chg, 0, sizeof(chg));
        memset(lazy, 0, sizeof(lazy));
        printf("Case %d:\n", ca);
        while(n --)
        {
            char op[2];
            scanf("%s", op);
            if(op[0] == 'I')
            {
                int l, r;
                scanf("%d %d", &l, &r);
                Update(l, r, 1, len, 1);
            }
            else
            {
                int x, num = 0;
                scanf("%d", &x);
                num = Query(x, x, 1, len, 1);
                if(num & 1)
                    printf("%d\n", (s[x] == '0') ? 1 : 0);
                else
                    printf("%d\n", (s[x] == '0') ? 0 : 1);
            }
        }
    }
}