题解 P5057 【[CQOI2006]简单题】

小粉兔 · 2018-12-02 00:25:43 · 题解

简单题，果然很简单。
考虑差分序列（用异或代替减法），则每个元素的真实值是差分序列的异或前缀和，修改的时候只需要改 l 和 r + 1 两个位置的差分。
用树状数组维护。

#include <cstdio>

int N, M, B[100001];
inline void A(int i) { for (; i <= N; i += i & -i) B[i] ^= 1; }
inline int Q(int i) { int A = 0; for (; i; i -= i & -i) A ^= B[i]; return A; }

int main() {
    scanf("%d%d", &N, &M);
    while (M--) {
        int opt, l, r;
        scanf("%d%d", &opt, &l);
        if (opt == 1) A(l), scanf("%d", &r), A(r + 1);
        else printf("%d\n", Q(l));
    }
    return 0;
}