一个奇怪的问题,求助大佬
查看原帖
一个奇怪的问题,求助大佬
31346
Fritz1149楼主2022/4/21 11:17

代码这样的

#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

2022/4/21 11:17
加载中...