社区讨论

update函数为啥加上`if (ql <= mid)`就会WA

P3372【模板】线段树 1参与者 4已保存回复 4

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@loczmqbd
此快照首次捕获于
2023/10/30 22:21
2 年前
此快照最后确认于
2023/11/05 08:40
2 年前
查看原帖
代码如下
CPP
inline void pushup(int rt) {
    v[rt] = v[ls[rt]] + v[rs[rt]];
}

inline void pushdown(int l, int r, int rt) {
    v[rt] += tag[rt] * (r - l + 1);
    if (l != r)
        tag[ls[rt]] += tag[rt],
        tag[rs[rt]] += tag[rt];
    tag[rt] = 0;
}
void update(int l, int r, int rt, int ql, int qr, long long xg) {
    pushdown(l, r, rt);
    if (ql > r || qr < l)
        return;
    if (ql <= l && qr >= r) {
        tag[rt] += xg;
        pushdown(l, r, rt);
        return;
    }
    int mid = (l + r) >> 1;
    // if (ql <= mid)
        update(l, mid, ls[rt], ql, qr, xg);
    // if (qr > mid)
        update(mid + 1, r, rs[rt], ql, qr, xg);
    pushup(rt);
}

long long query(int l, int r, int rt, int ql, int qr) {
    pushdown(l, r, rt);
    if (ql > r || qr < l)
        return 0;
    if (ql <= l && qr >= r)
        return v[rt];
    int mid = (l + r) >> 1;
    long long res = 0;
    if (ql <= mid)
        res += query(l, mid, ls[rt], ql, qr);
    if (qr > mid)
        res += query(mid + 1, r, rs[rt], ql, qr);
    return res;
}
update函数里有两个注释,去掉它们就会WA掉
但是如果是query函数里就完全没问题
萌新想知道是什么原理
不过还有几hh就CSP了 没人回答我就背代码了/kk

回复

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

正在加载回复...