刚刚发现乘法tag没有正常向下传递,大家有办法解决吗?
by ybc2027_yangshoukuo @ 2024-03-31 22:16:14
@[ybc2027_yangshoukuo](/user/1070523) 有一些根本性错误。
```cpp
void add_mul_tag(long long dl, long long dr, long long k, long long rt) {
down_update(rt, dl, dr);
tag_mul[rt] += k;
tree[rt] *= k;
}
```
这里 `add` 的 `tag` 也要 $*k$ 罢,因为 $(\times a + b)\times k=\times ak+bk$
by QWQ_123 @ 2024-03-31 22:18:50
@[ybc2027_yangshoukuo](/user/1070523) 还有在
`print_num`,`mul_num`,`qj_num`,函数中为什么只下传一个 `tag`
by QWQ_123 @ 2024-03-31 22:19:40
@[ybc2027_yangshoukuo](/user/1070523) 过了:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100005; //
long long n, m, tree[4 * N], a, b, c, d, z[N], tag[4 * N], tag_mul[4 * N], mod;
long long ls(long long k) {
return k * 2;
}
long long rs(long long k) {
return k * 2 + 1;
}
void up_update(long long rt) {
tree[rt] = tree[ls(rt)] + tree[rs(rt)];
tree[rt] %= mod;
}
void add_tag(long long dl, long long dr, long long k, long long rt) {
tag[rt] += k;
tag[rt] %= mod;
tree[rt] += (dr - dl + 1) * k % mod;
tree[rt] %= mod;
}
void down_update(long long rt, long long l, long long r) {
if (tag[rt] != 0) {
long long mid = (l + r) / 2;
add_tag(l, mid, tag[rt], ls(rt));
add_tag(mid + 1, r, tag[rt], rs(rt));
tag[rt] = 0;
}
return;
}
void add_mul_tag(long long dl, long long dr, long long k, long long rt) {
tag_mul[rt] *= k;
tag_mul[rt] %= mod;
tag[rt] *= k;
tag[rt] %= mod;
tree[rt] *= k;
tree[rt] %= mod;
}
void down_mul_update(long long rt, long long l, long long r) {
if (tag_mul[rt] != 1) {
long long mid = (l + r) / 2;
add_mul_tag(l, mid, tag_mul[rt], ls(rt));
add_mul_tag(mid + 1, r, tag_mul[rt], rs(rt));
tag_mul[rt] = 1;
}
return;
}
void begintree(long long l, long long r, long long rt) {
tag[rt] = 0;
tag_mul[rt] = 1;
if (l == r) {
tree[rt] = z[l];
return;
}
long long mid = (l + r) / 2;
begintree(l, mid, ls(rt));
begintree(mid + 1, r, rs(rt));
up_update(rt);
return;
}
void qj_num(long long dl, long long dr, long long l, long long r, long long k, long long rt) {
if (l <= dl && dr <= r) {
add_tag(dl, dr, k, rt);
return;
}
down_mul_update(rt, dl, dr);
down_update(rt, dl, dr);
long long mid = (dl + dr) / 2;
if (l <= mid) qj_num(dl, mid, l, r, k, ls(rt));
if (r > mid) qj_num(mid + 1, dr, l, r, k, rs(rt));
up_update(rt);
return;
}
void mul_num(long long dl, long long dr, long long l, long long r, long long k, long long rt) {
if (l <= dl && dr <= r) {
add_mul_tag(dl, dr, k, rt);
return;
}
down_mul_update(rt, dl, dr);
down_update(rt, dl, dr);
long long mid = (dl + dr) / 2;
if (l <= mid) mul_num(dl, mid, l, r, k, ls(rt));
if (r > mid) mul_num(mid + 1, dr, l, r, k, rs(rt));
up_update(rt);
return;
}
long long print_num(long long dl, long long dr, long long l, long long r, long long rt) {
if (l <= dl && dr <= r) {
return tree[rt];
}
down_mul_update(rt, dl, dr);
down_update(rt, dl, dr);
long long mid = (dl + dr) / 2, res = 0;
if (l <= mid) res += print_num(dl, mid, l, r, ls(rt));
res %= mod;
if (r > mid) res += print_num(mid + 1, dr, l, r, rs(rt));
res %= mod;
return res;
}
int main() {
scanf("%lld%lld%lld", &n, &m, &mod);
for (int i = 1; i <= n; i++) scanf("%lld", &z[i]);
begintree(1, n, 1);
for (int i = 1; i <= m; i++) {
scanf("%lld%lld%lld", &a, &b, &c);
if (a == 1) {
scanf("%lld", &d);
mul_num(1, n, b, c, d, 1);
} else if (a == 2) {
scanf("%lld", &d);
qj_num(1, n, b, c, d, 1);
} else {
printf("%lld\n", print_num(1, n, b, c, 1));
}
// printf("%lld\n", print_num(1, n, 2, 8, 1));
}
return 0;
}
```
by QWQ_123 @ 2024-03-31 22:30:17
感谢大佬!!!
by ybc2027_yangshoukuo @ 2024-03-31 22:38:41
我也过了,此题完结。\
**感谢大佬!**
by ybc2027_yangshoukuo @ 2024-03-31 22:49:05