代码这样的
#include <cstdio>
#define N 100000
#define ll long long
#define add(x, y, mod) x = (x + ((y) % mod)) % mod
#define multiply(x, y, mod) x = (x * ((y) % mod)) % mod
using namespace std;
ll val[4 * N + 5], tag[2][4 * N + 5], a[N + 5];
int mod;
enum type{
ADD,
MULTIPLY
};
void build(int l, int r, int p){
tag[MULTIPLY][p] = 1;
if(l == r){
val[p] = a[l];
return;
}
int mid = l + ((r - l) >> 1);
build(l, mid, p * 2);
build(mid + 1, r, p * 2 + 1);
val[p] = (val[p * 2] + val[p * 2 + 1]) % mod;
}
void push_down(int l, int r, int p){
if(l == r)
return;
int mid = l + ((r - l) >> 1);
// 就在这个位置有问题
if(tag[MULTIPLY][p]){
multiply(tag[MULTIPLY][p * 2], tag[MULTIPLY][p], mod);
multiply(tag[ADD][p * 2], tag[MULTIPLY][p], mod);
multiply(tag[MULTIPLY][p * 2 + 1], tag[MULTIPLY][p], mod);
multiply(tag[ADD][p * 2 + 1], tag[MULTIPLY][p], mod);
multiply(val[p * 2], tag[MULTIPLY][p], mod);
multiply(val[p * 2 + 1], tag[MULTIPLY][p], mod);
tag[MULTIPLY][p] = 1;
}
if(tag[ADD][p]){
add(tag[ADD][p * 2], tag[ADD][p], mod);
add(tag[ADD][p * 2 + 1], tag[ADD][p], mod);
add(val[p * 2], tag[ADD][p] * (mid - l + 1), mod);
add(val[p * 2 + 1], tag[ADD][p] * (r - mid), mod);
tag[ADD][p] = 0;
}
}
void update(int L, int R, int l, int r, int p, type t, ll v){
if(L <= l && r <= R){
if(t == ADD){
add(tag[ADD][p], v, mod);
add(val[p], (v % mod) * (r - l + 1), mod);
}
else{
multiply(tag[MULTIPLY][p], v, mod);
multiply(tag[ADD][p], v, mod);
multiply(val[p], v, mod);
}
return;
}
push_down(l, r, p);
int mid = l + ((r - l) >> 1);
if(L <= mid)
update(L, R, l, mid, p * 2, t, v);
if(R > mid)
update(L, R, mid + 1, r, p * 2 + 1, t, v);
val[p] = (val[p * 2] + val[p * 2 + 1]) % mod;
}
ll get_sum(int L, int R, int l, int r, int p){
if(L <= l && r <= R)
return val[p];
push_down(l, r, p);
int mid = l + ((r - l) >> 1);
ll ret = 0;
if(L <= mid)
add(ret, get_sum(L, R, l, mid, p * 2), mod);
if(R > mid)
add(ret, get_sum(L, R, mid + 1, r, p * 2 + 1), mod);
return ret;
}
void display(int l, int r, int p){
printf("[%d, %d]: tag_add: %lld, tag_mul: %lld, val: %lld\n", l, r, tag[ADD][p], tag[MULTIPLY][p], val[p]);
if(l == r)
return;
int mid = l + ((r - l) >> 1);
display(l, mid, p * 2);
display(mid + 1, r, p * 2 + 1);
}
int n, m;
int main(){
scanf("%d%d%d", &n, &m, &mod);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
build(1, n, 1);
for(int i = 0; i < m; i++){
int op;
scanf("%d", &op);
if(op == 1){
int x, y;
ll k;
scanf("%d%d%lld", &x, &y, &k);
update(x, y, 1, n, 1, MULTIPLY, k);
}
else if(op == 2){
int x, y;
ll k;
scanf("%d%d%lld", &x, &y, &k);
update(x, y, 1, n, 1, ADD, k);
}
else{
int x, y;
scanf("%d%d", &x, &y);
printf("%lld\n", get_sum(x, y, 1, n, 1));
}
// display(1, n, 1);
// printf("\n");
}
return 0;
}
在 push down 这个函数中,处理乘法标记下传的部分,如果把判断条件定为 if(tag[MULTIPLY][p] != 1) 那么就会ac,但是如果像贴的代码这么写 if(tag[MULTIPLY][p]) 就会wa,我知道如果这么写其实起不到筛选的效果,但是我觉得也不会造成错误吧...?
我想来想去想不出原因,求大佬解惑!orz