已经过了,问题出在:
我这个pushdown每次只会修改当前节点的sum值并把乘和加的懒标记下传。
这样当我执行修改操作时可能只选择了某个节点u的右儿子进行修改,当前右儿子的sum值是完全正确的(它正确地把前往他的路径上的所有懒标记都继承了下来),此时某个节点u的左儿子虽然也随着pushdown继承了懒标记,但是它并没有sum值的更新。所以在pushup(u)的时候就会出问题,因为使用了尚未更新的左儿子的sum。
解决办法:
在pushup前再多pushdown一下左儿子和右儿子即可。
AC代码:
```cpp
#include <iostream>
#define int long long
using namespace std;
const int N = 1e5 + 10;
struct Node {
int l, r, k, b, sum;
}node[N * 4];
int n, p, m;
int a[N];
void pushup(int u) {
node[u].sum = (node[u << 1].sum + node[u << 1 | 1].sum) % p;
}
void pushdown(int u) {
node[u].sum = (node[u].sum * node[u].k % p + node[u].b * (node[u].r - node[u].l + 1) % p) % p;
if (node[u].l != node[u].r) {
node[u << 1].k = (node[u << 1].k * node[u].k) % p;
node[u << 1].b = (node[u << 1].b * node[u].k % p + node[u].b) % p;
node[u << 1 | 1].k = (node[u << 1 | 1].k * node[u].k) % p;
node[u << 1 | 1].b = (node[u << 1 | 1].b * node[u].k % p + node[u].b) % p;
}
node[u].k = 1, node[u].b = 0;
}
void build(int u, int l, int r) {
node[u] = {l, r, 1, 0, 0};
if (l == r) {
node[u].sum = a[l] % p;
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void add(int u, int l, int r, int c) {
if (node[u].l >= l && node[u].r <= r) {
node[u].b = (node[u].b + c) % p;
pushdown(u);
return;
}
pushdown(u);
int mid = node[u].l + node[u].r >> 1;
if (mid >= l) add(u << 1, l, r, c);
if (mid < r) add(u << 1 | 1, l, r, c);
pushdown(u << 1);
pushdown(u << 1 | 1);
pushup(u);
}
void multiply(int u, int l, int r, int c) {
if (node[u].l >= l && node[u].r <= r) {
node[u].k = (node[u].k * c) % p;
node[u].b = (node[u].b * c) % p;
pushdown(u);
return;
}
pushdown(u);
int mid = node[u].l + node[u].r >> 1;
if (mid >= l) multiply(u << 1, l, r, c);
if (mid < r) multiply(u << 1 | 1, l, r, c);
pushdown(u << 1);
pushdown(u << 1 | 1);
pushup(u);
}
int query(int u, int l, int r) {
if (node[u].l >= l && node[u].r <= r) {
pushdown(u);
// cout << "shabi:" << node[u].sum << endl;
return node[u].sum % p;
}
pushdown(u);
int res = 0;
int mid = node[u].l + node[u].r >> 1;
if (mid >= l) res = (res + query(u << 1, l, r)) % p;
if (mid < r) res = (res + query(u << 1 | 1, l, r)) % p;
return res;
}
signed main() {
scanf("%lld%lld", &n, &p);
for (int i = 1; i <= n; i ++) {
scanf("%lld", &a[i]);
}
scanf("%lld", &m);
build(1, 1, n);
while (m --) {
int op;
int t, g, c;
scanf("%lld", &op);
if (op == 1) {
scanf("%lld%lld%lld", &t, &g, &c);
multiply(1, t, g, c);
}
else if (op == 2) {
scanf("%lld%lld%lld", &t, &g, &c);
add(1, t, g, c);
}
else {
scanf("%lld%lld", &t, &g);
printf("%lld\n", query(1, t, g) % p);
}
}
return 0;
}
```
by lightmon @ 2023-11-04 02:55:03