校门外的树

题目描述

思路

题目的意思是在[l, r]的所有整数位置都种树，每个点可以重复种，问[L, R]的树有多少种
一个树状数组start保存l，一个树状数组end保存r，保存的方式就是从update(x, 1)
start 表示从l开始就可以种树了，end 表示从r就不可以种树了
sum函数 求得就是满足要求的点有多少个
这样[L, R]的结果就是 sum(R, start) - sum(L - 1, end)，能够开始的种树点 - 必须结束的种树的点

代码

#include <cstdio>
#include <cstring>
int n, m;
int arrSt[51000], arrEd[51000];
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;
}
int lowbit(int x) {
    return x & (-x);
}
void update(int x, int y, int * arr) {
    while (x <= n) {
        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, a, b, c; i <= m; ++i) {
        a = read(), b = read(), c = read();
        // printf("%d %d %d\n", a, b, c);
        if (a == 1) update(b, 1, arrSt), update(c + 1, 1, arrEd);
        else printf("%d\n", sum(c, arrSt) - sum(b, arrEd));
    }
    return 0;
}

校门外的树

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