求助指针线段树
  • 板块学术版
  • 楼主Grisses
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/1/26 15:57
  • 上次更新2023/10/28 10:52:47
查看原帖
求助指针线段树
428358
Grisses楼主2022/1/26 15:57

有没有哪位大佬帮忙看看我的线段树,不知为何一直RE

#include <bits/stdc++.h>
using namespace std;
namespace STL {
#define int long long
struct SegmentTree {
    struct Node {
        int l, r, val, minn, maxn, p;
        Node *L, *R;
        Node() { l = r = val = minn = maxn = p = 0LL; }
    } * Root = new Node;
    bool B_sum, B_max, B_min;
    int Section[];
    void Down(Node* q) {
        if (q->p != 0 && q->l != q->r) {
            if (B_sum) {
                q->L->val += (q->L->r - q->L->l + 1) * (q->p);
                q->R->val += (q->R->r - q->R->l + 1) * (q->p);
            }
            if (B_max) {
                q->L->maxn += q->p;
                q->R->maxn += q->p;
            }
            if (B_min) {
                q->L->minn += q->p;
                q->R->minn += q->p;
            }
            q->L->p += q->p;
            q->R->p += q->p;
        }
        q->p = 0;
    }
    void Build(Node* q, int l, int r) {
        q->l = l, q->r = r, q->p = 0;
        if (l == r) {
            q->L = q->R = NULL;
            if (B_sum)
                q->val = Section[l];
            if (B_max)
                q->maxn = Section[l];
            if (B_min)
                q->minn = Section[l];
            return;
        }
        int mid = l + r >> 1;
        q->L = new Node;
        q->R = new Node;
        Build(q->L, l, mid);
        Build(q->R, mid + 1, r);
        if (B_sum)
            q->val = (q->L->val) + (q->R->val);
        if (B_max)
            q->maxn = max(q->L->maxn, q->R->maxn);
        if (B_min)
            q->minn = min(q->L->minn, q->R->minn);
    }
    void Build(int l, int r, int a[], bool b1, bool b2, bool b3) {
        B_sum = b1, B_max = b2, B_min = b3;
        for (int i = l; i <= r; i++) Section[i] = a[i];
        Build(Root = new Node, l, r);
    }
    void add(Node* q, int x, int y) {
        if (q->l == q->r) {
            if (B_sum)
                q->val += y;
            if (B_max)
                q->maxn += y;
            if (B_min)
                q->minn += y;
            return;
        }
        int mid = (q->l + q->r) >> 1;
        if (x <= mid)
            add(q->L, x, y);
        else
            add(q->R, x, y);
        if (B_sum)
            q->val += y;
        if (B_max)
            q->maxn = max(q->L->maxn, q->R->maxn);
        if (B_min)
            q->minn = min(q->L->minn, q->R->minn);
    }
    void Add(int x, int y) { add(Root, x, y); }
    void add(Node* q, int l, int r, int x) {
        if (l <= q->l && q->r <= r) {
            if (B_sum)
                q->val += (q->r - q->l + 1) * x;
            if (B_max)
                q->maxn += x;
            if (B_min)
                q->minn += x;
            q->p += x;
            return;
        }
        Down(q);
        int mid = (q->l + q->r) >> 1;
        if (l <= mid)
            add(q->L, l, r, x);
        if (mid < r)
            add(q->R, l, r, x);
        if (B_sum)
            q->val = q->L->val + q->R->val;
        if (B_max)
            q->maxn = max(q->L->maxn, q->R->maxn);
        if (B_min)
            q->minn = min(q->L->minn, q->R->minn);
    }
    void Add(int l, int r, int x) { add(Root, l, r, x); }
    int Getsum(Node* q, int l, int r) {
        if (l <= (q->l) && (q->r) <= r)
            return (q->val);
        Down(q);
        int sum = 0, mid = (q->l + q->r) >> 1;
        if (l <= mid)
            sum += Getsum(q->L, l, r);
        if (mid < r)
            sum += Getsum(q->R, l, r);
        return sum;
    }
    int Getsum(int l, int r) { return Getsum(Root, l, r); }
    int Getmax(Node* q, int l, int r) {
        if (l <= q->l && q->r <= r)
            return q->maxn;
        Down(q);
        int sum = -9e18, mid = (q->l + q->r) >> 1;
        if (l <= mid)
            sum = max(sum, Getmax(q->L, l, r));
        if (mid < r)
            sum = max(sum, Getmax(q->R, l, r));
        return sum;
    }
    int Getmax(int l, int r) { return Getmax(Root, l, r); }
    int Getmin(Node* q, int l, int r) {
        if (l <= q->l && q->r <= r)
            return q->minn;
        Down(q);
        int sum = 9e18, mid = (q->l + q->r) >> 1;
        if (l <= mid)
            sum = min(sum, Getmin(q->L, l, r));
        if (mid < r)
            sum = min(sum, Getmin(q->R, l, r));
        return sum;
    }
    int Getmin(int l, int r) { return Getmin(Root, l, r); }
};
#undef int
}  // namespace STL
using namespace STL;
long long int n, m;
long long int a[100005];
signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    SegmentTree T;
    T.Build(1, n, a, 1, 0, 0);
    long long int op, l, r, k;
    while (m--) {
        scanf("%lld%lld%lld", &op, &l, &r);
        if (op == 1) {
            scanf("%lld", &k);
            T.Add(l, r, k);
        } else {
            printf("%lld\n", T.Getsum(l, r));
        }
    }
    return 0;
}

2022/1/26 15:57
加载中...