(线段树)为什么减去无效的pushdown会错
查看原帖
(线段树)为什么减去无效的pushdown会错
59057
Smile_laughter楼主2023/11/28 13:29

两篇代码一个100,一个70,唯一区别是三处pushdown函数调用前有个if判断:

if(add[p]||mul[p]>1){

    down(s,t,p);
}

add数组是加法的lazy标记,mul数组是乘法的lazy标记,p是当前区间的序号,down就是lazy标记下移的函数,s,t是当前区间的左右端点

add[p]==0时就不需要pushdown吧,同样mul[p]==1时,那为什么会多WA三个点呢

这是100分的

#include <iostream>
#include <cstdio>
#include <string>
#define N 200003
#define ll long long
#define int long long
ll mod;
int l,r,k;
using namespace std;
long long read() {//long long 类型是真的坑
    long long x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w; 
}
ll d[N*4],a[N],add[N*4],mul[N*4];

void build(int s,int t,int p){
    mul[p]=1;
    if(s==t){
        d[p]=a[s]%mod;
        return;
    }
    int m=s+((t-s)>>1);
    build(s,m,p<<1);
    build(m+1,t,(p<<1)+1);
    d[p]=(d[p<<1]+d[p<<1|1])%mod;
}
void down(int s,int t,int p){

    d[p<<1]*=mul[p];d[(p<<1)+1]*=mul[p];
    d[p<<1]%=mod;d[(p<<1)+1]%=mod;
    mul[p<<1]*=mul[p];mul[(p<<1)+1]*=mul[p];
    mul[p<<1]%=mod;mul[(p<<1)+1]%=mod;
        
    
    int m=s+((t-s)>>1);
    add[p<<1]=(add[p<<1]*mul[p]+add[p])%mod;
    add[p<<1|1]=(add[p<<1|1]*mul[p]+add[p])%mod;
    //add[p<<1]%=mod;add[(p<<1)+1]%=mod;
    d[p<<1]+=add[p]*(m-s+1);
    d[(p<<1)+1]+=add[p]*(t-m);
    d[p<<1]%=mod;d[(p<<1)+1]%=mod;
    add[p]=0;
    mul[p]=1;   
}
void Add(int s,int t,int p){
    
    if(l<=s&&r>=t){
        d[p]+=(t-s+1)*k;
        d[p]%=mod;
        add[p]+=k;
        add[p]%=mod;
        return;
    }
    int m=s+((t-s)>>1);

        down(s,t,p);
    
    
    if(l<=m)Add(s,m,p<<1);
    if(r>m)Add(m+1,t,(p<<1)+1);
    d[p]=d[p<<1]+d[(p<<1)+1];
    d[p]%=mod;
}
void Mul(int s,int t,int p){
    int m=s+((t-s)>>1);
    if(l<=s&&r>=t){
        add[p]=(add[p]*k)%mod;
        d[p]*=k;
        d[p]%=mod;
        mul[p]*=k;
        mul[p]%=mod;
        return;
    }
  
        down(s,t,p);

    
    if(l<=m)Mul(s,m,p<<1);
    if(r>m)Mul(m+1,t,(p<<1)+1);
    d[p]=d[p<<1]+d[(p<<1)+1];
    d[p]%=mod;
}
ll getsum(int s,int t,int p){
    //??????????
    if(l<=s&&r>=t)return d[p]%mod;
    int m=s+((t-s)>>1);
    
    down(s,t,p);
    ll sum=0;
    
    if(l<=m)sum=getsum(s,m,p<<1)%mod;
    if(r>m)sum+=getsum(m+1,t,(p<<1)+1)%mod;
    return sum%mod;
}
signed main()
{
    int n=read(),q=read();
    mod=read();
    for(int i=1;i<=n;++i)a[i]=read();
    build(1,n,1);
    while(q--){
        int opt=read();
        l=read(),r=read();
        if(opt==1){
            k=read();
            Mul(1,n,1);
        }
        else if(opt==2){
            k=read();
            Add(1,n,1);
        }
        else {
            printf("%lld\n",getsum(1,n,1));
        }
    }
    return 0;
}

这是70分的

#include <iostream>
#include <cstdio>
#include <string>
#define N 200003
#define ll long long
#define int long long
ll mod;
int l,r,k;
using namespace std;
long long read() {//long long 类型是真的坑
    long long x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w; 
}
ll d[N*4],a[N],add[N*4],mul[N*4];

void build(int s,int t,int p){
    mul[p]=1;
    if(s==t){
        d[p]=a[s]%mod;
        return;
    }
    int m=s+((t-s)>>1);
    build(s,m,p<<1);
    build(m+1,t,(p<<1)+1);
    d[p]=(d[p<<1]+d[p<<1|1])%mod;
}
void down(int s,int t,int p){

    d[p<<1]*=mul[p];d[(p<<1)+1]*=mul[p];
    d[p<<1]%=mod;d[(p<<1)+1]%=mod;
    mul[p<<1]*=mul[p];mul[(p<<1)+1]*=mul[p];
    mul[p<<1]%=mod;mul[(p<<1)+1]%=mod;
        
    
    int m=s+((t-s)>>1);
    add[p<<1]=(add[p<<1]*mul[p]+add[p])%mod;
    add[p<<1|1]=(add[p<<1|1]*mul[p]+add[p])%mod;
    //add[p<<1]%=mod;add[(p<<1)+1]%=mod;
    d[p<<1]+=add[p]*(m-s+1);
    d[(p<<1)+1]+=add[p]*(t-m);
    d[p<<1]%=mod;d[(p<<1)+1]%=mod;
    add[p]=0;
    mul[p]=1;   
}
void Add(int s,int t,int p){
    
    if(l<=s&&r>=t){
        d[p]+=(t-s+1)*k;
        d[p]%=mod;
        add[p]+=k;
        add[p]%=mod;
        return;
    }
    int m=s+((t-s)>>1);
    if(add[p]||mul[p]>1){
        down(s,t,p);
    }
    
    if(l<=m)Add(s,m,p<<1);
    if(r>m)Add(m+1,t,(p<<1)+1);
    d[p]=d[p<<1]+d[(p<<1)+1];
    d[p]%=mod;
}
void Mul(int s,int t,int p){
    int m=s+((t-s)>>1);
    if(l<=s&&r>=t){
        add[p]=(add[p]*k)%mod;
        d[p]*=k;
        d[p]%=mod;
        mul[p]*=k;
        mul[p]%=mod;
        return;
    }
    if(add[p]||mul[p]>1){
        down(s,t,p);
    }
    
    if(l<=m)Mul(s,m,p<<1);
    if(r>m)Mul(m+1,t,(p<<1)+1);
    d[p]=d[p<<1]+d[(p<<1)+1];
    d[p]%=mod;
}
ll getsum(int s,int t,int p){
    //??????????
    if(l<=s&&r>=t)return d[p]%mod;
    int m=s+((t-s)>>1);
    
    if(add[p]||mul[p]>1)down(s,t,p);
    ll sum=0;
    
    if(l<=m)sum=getsum(s,m,p<<1)%mod;
    if(r>m)sum+=getsum(m+1,t,(p<<1)+1)%mod;
    return sum%mod;
}
signed main()
{
    int n=read(),q=read();
    mod=read();
    for(int i=1;i<=n;++i)a[i]=read();
    build(1,n,1);
    while(q--){
        int opt=read();
        l=read(),r=read();
        if(opt==1){
            k=read();
            Mul(1,n,1);
        }
        else if(opt==2){
            k=read();
            Add(1,n,1);
        }
        else {
            printf("%lld\n",getsum(1,n,1));
        }
    }
    return 0;
}
2023/11/28 13:29
加载中...