社区讨论

怎么把函数当参数传到函数里

灌水区参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lzo5o3dl
此快照首次捕获于
2024/08/10 21:12
2 年前
此快照最后确认于
2024/08/10 22:16
2 年前
查看原帖
想水一个线段树模板
CPP

#include <vector>
#include <iostream>
using namespace std;

template<typename T>
struct SegmentTree {
public:
    vector<T> arr;
    vector<T> tree;
    vector<T> tag;

    inline size_t ls(size_t x) const { return x << 1; }
    inline size_t rs(size_t x) const { return x << 1 | 1; }

    void push_up(size_t p) {
        tree[p] = tree[ls(p)] + tree[rs(p)];
    }

    void build(size_t p, size_t l, size_t r) {
        tag[p] = 0;
        if (l == r) {
            tree[p] = arr[l];
            return;
        }
        size_t mid = (l + r) >> 1;
        build(ls(p), l, mid);
        build(rs(p), mid + 1, r);
        push_up(p);
    }

    inline void apply_tag(size_t p, size_t l, size_t r, T k) {
        tag[p] += k;
        tree[p] += k * (r - l + 1);
    }

    void push_down(size_t p, size_t l, size_t r) {
        size_t mid = (l + r) >> 1;
        apply_tag(ls(p), l, mid, tag[p]);
        apply_tag(rs(p), mid + 1, r, tag[p]);
        tag[p] = 0;
    }

    void update(size_t p, size_t nl, size_t nr, size_t l, size_t r, T k) {
        if (nl <= l && r <= nr) {
            apply_tag(p, l, r, k);
            return;
        }
        push_down(p, l, r);
        size_t mid = (l + r) >> 1;
        if (nl <= mid) update(ls(p), nl, nr, l, mid, k);
        if (nr > mid) update(rs(p), nl, nr, mid + 1, r, k);
        push_up(p);
    }

    T query(size_t p, size_t x, size_t y, size_t l, size_t r) {
        if (x <= l && r <= y) return tree[p];
        size_t mid = (l + r) >> 1;
        push_down(p, l, r);
        T res = 0;
        if (x <= mid) res += query(ls(p), x, y, l, mid);
        if (y > mid) res += query(rs(p), x, y, mid + 1, r);
        return res;
    }

public:
    SegmentTree(size_t size)
        : arr(size + 1), tree(4 * size), tag(4 * size) {}
};

int main() {
    size_t n, m;
    cin >> n >> m;
    SegmentTree<long long> tree(n);
    for (size_t i = 1; i <= n; i++) {
        cin >> tree.arr[i];
    }
    tree.build(1, 1, n);
    while (m--) {
        int o;
        cin >> o;
        if (o == 1) {
            int x, y, k;
            cin >> x >> y >> k;
            tree.update(1, x, y, 1, n, k);
        }
        else {
            int x, y;
            cin >> x >> y;
            cout << tree.query(1, x, y, 1, n) << endl;
        }
    }
    return 0;
}
本来想让每个函数传进去一个函数,自定义线段树的 行为,但是我不知道怎么传函数进去。所以有大佬会吗。

回复

0 条回复,欢迎继续交流。

正在加载回复...