玄学问题（玄关

在线段树中

void pushdown(int u,int l,int r){
    int m=(l+r)>>1;
    mark(u*2,l,m,lza[u],2);
    mark(u*2,l,m,lzm[u],1);
    mark(u*2+1,m+1,r,lza[u],2);
    mark(u*2+1,m+1,r,lzm[u],1);
    lzm[u]=1;
    lza[u]=0;
}

是错的

void pushdown(int u,int l,int r){
    int m=(l+r)>>1;
    mark(u*2,l,m,lzm[u],1);
    mark(u*2,l,m,lza[u],2);
    mark(u*2+1,m+1,r,lzm[u],1);
    mark(u*2+1,m+1,r,lza[u],2);
    lza[u]=0;
    lzm[u]=1;
}

是对的

为什么???

完整AC code

题目

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+10;
#define int long long
int n,q,mod,x,y,k,a[N],opt;
int w[N],lzm[N],lza[N];
void pushup(int u){
    w[u]=(w[u*2]+w[u*2+1])%mod;
}
void build(int u,int l,int r){
    if(l==r){
        w[u]=a[l];
        return ;
    }
    lzm[u]=1;
    int m=(l+r)>>1;
    build(u*2,l,m);
    build(u*2+1,m+1,r);
    pushup(u);
}
bool in(int l,int r,int x,int y){
    return (x<=l)&&(y>=r);
}
bool out(int l,int r,int x,int y){
    return (x>r)||(y<l);
}
void mark(int u,int l,int r,int p,int op){
    if(op==1){
        (lzm[u]*=p)%=mod;
        (lza[u]*=p)%=mod;
        (w[u]*=p)%=mod;
    }
    else {
        (lza[u]+=p)%=mod;
        (w[u]+=(r-l+1)*p)%=mod;
    }
}
void pushdown(int u,int l,int r){
    int m=(l+r)>>1;
    mark(u*2,l,m,lzm[u],1);
    mark(u*2,l,m,lza[u],2);
    mark(u*2+1,m+1,r,lzm[u],1);
    mark(u*2+1,m+1,r,lza[u],2);
    lza[u]=0;
    lzm[u]=1;
}
int query(int u,int l,int r,int x,int y){
    if(in(l,r,x,y)){
        return w[u];
    }
    else if(!out(l,r,x,y)){
        int m=(l+r)>>1;
        pushdown(u,l,r);
        return (query(u*2,l,m,x,y)%mod+query(u*2+1,m+1,r,x,y)%mod)%mod;
    }
    else return 0;
}
void update(int u,int l,int r,int x,int y,int p,int op){
    if(in(l,r,x,y)){
        mark(u,l,r,p,op);
    }
    else if(!out(l,r,x,y)){
        int m=(l+r)>>1;
        pushdown(u,l,r);
        update(u*2,l,m,x,y,p,op);
        update(u*2+1,m+1,r,x,y,p,op);
        pushup(u);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q>>mod;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(q--){
        cin>>opt;
        if(opt==1){
            cin>>x>>y>>k;
            update(1,1,n,x,y,k,1);
        }
        else if(opt==2){
            cin>>x>>y>>k;
            update(1,1,n,x,y,k,2);
        }
        else {
            cin>>x>>y;
            cout<<query(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}