萌新刚学FHQ,输出全0求助

P3372 【模板】线段树 1

Saka_Noa @ 2023-09-21 15:03:12

#include<bits/stdc++.h>
using namespace std;
#define ls(x) FHQ[x].Son[0]
#define rs(x) FHQ[x].Son[1]
#define vl(x) FHQ[x].val
#define si(x) FHQ[x].si
#define sm(x) FHQ[x].sum
#define tg(x) FHQ[x].tag
#define rr int r1 = 0, int r2 = 0, int r3 = 0
#define rp(i, a, b) for(int i = a;i <= b;i++)
const int N = 1e5 + 50;
struct Tree{ 
    int pri, Son[2], si;
    long long val, sum, tag; 
} FHQ[N];
int cnt, root, x, n, m, opt, l, r;
int new_node(int v) {
    FHQ[++cnt] = Tree{rand(), {0, 0}, 1, v, v, 0};
    return cnt;
}
void update(int x) {
    si(x) = si(ls(x)) + si(rs(x)) + 1;
    sm(x) = sm(ls(x)) + sm(rs(x)); 
}
void pushdown(int x) {
    if(!tg(x)) return;
    sm(ls(x)) += si(ls(x)) * tg(x);
    sm(rs(x)) += si(rs(x)) * tg(x);
    vl(ls(x)) += tg(x);
    vl(rs(x)) += tg(x);
    tg(ls(x)) += tg(x);
    tg(rs(x)) += tg(x);
    tg(x) = 0;
}
void split(int x, int k, int &a, int &b) {
    if(!x) return (void)(a = b = 0);
    pushdown(x);
    if(k <= si(ls(x))) {
        b = x;
        split(ls(x), k, a, ls(x));  
    } else {
        a = x;
        k -= si(ls(x)) + 1;
        split(rs(x), k, rs(x), b);
    }
    update(x);
}
int merge(int x, int y) {
    if(!x || !y) return x + y;
    pushdown(x);
    pushdown(y);
    if(FHQ[x].pri < FHQ[x].pri) {
        rs(x) = merge(rs(x), y);
        update(x);
        return x;
    } else {
        ls(y) = merge(x, ls(y));
        update(y);
        return y; 
    }
}
void insert(long long v) {
    root = merge(root, new_node(v));
}
void modify(int x, int y, long long v, rr) {
    split(root, x - 1, r1, r2);
    split(r2, y - x + 1, r2, r3);
    tg(r2) += v;
    vl(r2) += v;
    sm(r2) += v * si(r2);
    root = merge(r1, merge(r2, r3));
}
long long query(int x, int y, rr) {
    split(root, x - 1, r1, r2);
    split(r2, y - x + 1, r2, r3);
    long long ans = sm(r2);
    root = merge(r1, merge(r2, r3));
    return ans;
}
int main() {
    srand(time(0));
    scanf("%d %d", &n, &m);
    rp(i, 1, n) scanf("%d", &x), insert(x);
    rp(i, 1, m) {
        scanf("%d %d %d", &opt, &l, &r);
        if(opt == 1) {
            scanf("%d", &x);
            modify(l, r, x);
        } else 
        printf("%lld\n", query(l, r));
    }
    return 0;
}

by LgxTpre @ 2023-09-21 15:12:51

@Saka_Noa 先说个小错误,你的 52 行在干什么


by LgxTpre @ 2023-09-21 15:14:47

@Saka_Noa 第 23 行

sm(x) = sm(ls(x)) + sm(rs(x)) + vl(x); 

by Saka_Noa @ 2023-09-21 15:27:06

@LgxTpre 感激不尽,调过了


|