简单题

题目描述

思路

因为树状数组update是会一直更新到最后的节点，查询的也是端点的情况，所以用两个树状数组来维护一段区间
每次给定一个区间(l, r)变换, 就是update(l, 1, start), update(r, 1, ed)
注意 update(r, 1, ed), 而不是update(r + 1, 1, ed), 在查询[r+ 1, r+ 1]会出现有树的情况，实际上应该没有树
查询区间(L, R)，就是sum(R, start) - sum(L - 1, ed)

代码

#include <cstdio>
#include <cstring>
int arrSt[100005], arrEd[100005];
int n, m, lowbit[100005];
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s;
}

void update(int x, int y, int * arr) {
    while (x <= n + 1) {
        arr[x] += y;
        x += lowbit[x];
    }
}
int sum(int x, int * arr) {
    int res = 0;
    while (x) {
        res += arr[x];
        x -= lowbit[x];
    }
    return res;
}
int main() {
    n = read(), m = read();
    for (int i = 1; i <= n + 1; ++i) {
        lowbit[i] = i & (-i);
    }
    for (int i = 1, a, b, c; i <= m; ++i) {
        a = read();
        if (a == 1) {
            b = read(), c = read();
            update(b, 1, arrSt), update(c, 1, arrEd);
        } else {
            b = read();
            if ((sum(b, arrSt) - sum(b - 1, arrEd)) % 2 == 0) puts("0");
            else puts("1");
        }
    }
    return 0;
}

简单题

原文：https://www.cnblogs.com/liuzz-20180701/p/11489554.html