我个人不建议用 zkw 线段树实现带区间修改标记的线段树,很难记忆而且局限性很大
by 小粉兔 @ 2024-04-23 23:48:59
我个人不建议在不能自己熟练推出写法的情况下用 zkw 线段树实现带区间修改标记的线段树,很难记忆而且局限性很大
但能自己推的话,这玩意会有一种纯正重工业艺术,我个人还是建议写的
by UnyieldingTrilobite @ 2024-04-23 23:51:27
@[小粉兔](/user/10703) 谢谢建议。但是因为学校OJ太慢了,使用普通线段树根本无法通过[天天爱打卡](https://www.luogu.com.cn/problem/P9871)这道题目,所以想试一下常数较小的zkw线段树,结果发现网上很多代码都有bug。
by nb_jzy @ 2024-04-23 23:54:34
```cpp
ll d[maxn << 2], f[maxn], sum[maxn];
int c, t, n, m, k, M = 1, p = 0, b[maxn]; ll D;
inline void upd(re int x) {
ll tmp = max(d[x << 1], d[x << 1 | 1]);
if (!tmp) return;
d[x << 1] -= tmp; d[x << 1 | 1] -= tmp;
d[x] += tmp;
}
inline void mdf(re int l, re int r, ll k) {
for (l = l + M - 1, r = r + M + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (~l & 1) d[l ^ 1] += k;
if (r & 1) d[r ^ 1] += k;
upd(l >> 1), upd(r >> 1);
}
for (; l != 1; l >>= 1) upd(l >> 1);
}
inline ll qry(re int l, re int r) {
ll la = 0, ra = 0; l += M, r += M;
for (; (l ^ r) > 1; l >>= 1, r >>= 1) {
la += d[l], ra += d[r];
if (~l & 1) la = max(la, d[l ^ 1]);
if (r & 1) ra = max(ra, d[r ^ 1]);
}
ll ans = max(la + d[l], ra + d[r]);
while (l > 1) ans += d[l >>= 1];
return ans;
}
```
话说你怎么也用 zkw 树过的天天爱打卡。
by strcmp @ 2024-04-24 07:04:50
挖个墙角
by qyt1214 @ 2024-04-24 07:49:36
學習 AtCoder Library 的那種寫法,非常好記,而且封裝也比較完善。
by EarthMessenger @ 2024-04-24 09:54:57
@[nb_jzy](/user/561253) zhw不是讲过吗
by emo_male_god @ 2024-04-24 15:45:07
@[emo_male_god](/user/798157) 不是 jhr 吗?
by MYLHF @ 2024-04-24 22:32:27