社区讨论
update函数为啥加上`if (ql <= mid)`就会WA
P3372【模板】线段树 1参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @loczmqbd
- 此快照首次捕获于
- 2023/10/30 22:21 2 年前
- 此快照最后确认于
- 2023/11/05 08:40 2 年前
代码如下
CPPinline 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函数里就完全没问题萌新想知道是什么原理
不过还有几就CSP了 没人回答我就背代码了/kk
回复
共 4 条回复,欢迎继续交流。
正在加载回复...