P3373 【模板】线段树 2的一些问题

回复帖子

@Andykpa 2018-03-13 22:54 回复

请问我到底哪里错了啊,改了好久了

#include <iostream>
#include <cmath>
using namespace std;
const long long maxn=100000;
long long add[maxn<<2],sum[maxn<<2],add2[maxn<<2];
long long n,m;
long long a[maxn];
long long mod;
inline void Pushup(long long rt){
    (sum[rt]=(sum[rt<<1]+sum[rt<<1|1]))%mod;
}

inline void Build(long long l,long long r,long long rt){
    add[rt]=0;
        add2[rt]=1;
     if(l==r){
    sum[rt]=a[l];
    return ;
     }
     long long m=(l+r)>>1;
     Build(l,m,rt<<1);
     Build(m+1,r,rt<<1|1);
     Pushup(rt);
}

inline void Pushdown(long long rt,long long ln,long long rn){
    if(add[rt] || add2[rt]!=1){
    add2[rt<<1]*=add2[rt]%mod;
    add2[rt<<1|1]*=add2[rt]%mod;
    add[rt<<1]*=add2[rt]%mod;
    add[rt<<1|1]*=add2[rt]%mod;
    sum[rt<<1]*=add2[rt]%mod;
    sum[rt<<1|1]*=add2[rt]%mod;
    add2[rt]=1;
    (add[rt<<1]+=add[rt])%mod;
    (add[rt<<1|1]+=add[rt])%mod;
    (sum[rt<<1]+=add[rt]*ln)%mod;
    (sum[rt<<1|1]+=add[rt]*rn)%mod;
    add[rt]=0;
    }
}

inline void Update(long long L,long long R,long long C,long long l,long long r,long long rt){
     if(L<=l && r<=R){
    (sum[rt]+=C*(r-l+1))%mod;
    (add[rt]+=C)%mod;
    return ;
     }
     long long m=(l+r)>>1;
     Pushdown(rt,m-l+1,r-m);
     if(L<=m)Update(L,R,C,l,m,rt<<1);
     if(R>m)Update(L,R,C,m+1,r,rt<<1|1);
     Pushup(rt);
}

inline void Update2(long long L,long long R,long long C,long long l,long long r,long long rt){
     if(L<=l && r<=R){
    (sum[rt]*=C)%mod;
    (add[rt]*=C)%mod;
    (add2[rt]*=C)%mod;
    return ;
     }
     long long m=(l+r)>>1;
     Pushdown(rt,m-l+1,r-m);
     if(L<=m)Update2(L,R,C,l,m,rt<<1);
     if(R>m)Update2(L,R,C,m+1,r,rt<<1|1);
     Pushup(rt);
}

inline long long Query(long long L,long long R,long long l,long long r,long long rt){

    if(L<=l && r<=R){
    return sum[rt]%mod;
    }

    long long m=(l+r)>>1;
    long long ans=0;
    Pushdown(rt,m-l+1,r-m);
    if(L<=m)ans+=Query(L,R,l,m,rt<<1);
    if(R>m)ans+=Query(L,R,m+1,r,rt<<1|1);
    return ans;
}

int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);

   cin>>n>>m>>mod;

   long long x,y,z,e,f;

   for(register long long i=1;i<=n;i++){
        cin>>a[i];
   }

   Build(1,n,1);

   for(register long long i=1;i<=m;i++){
    long long k;
    cin>>k;
    if(k==1){
      cin>>x>>y>>z;
      Update2(x,y,z,1,n,1);
    }
    else if(k==2){
      cin>>x>>y>>z;
      Update(x,y,z,1,n,1);
    }
    else if(k==3){
        cin>>e>>f;
     long long Ans=Query(e,f,1,n,1);
      cout<<Ans%mod;
      cout<<endl;
    }
   }
   return 0;
}

感谢不尽

@Andykpa 2018-03-13 22:55 回复

我重新发一个

#include <iostream>
#include <cmath>
using namespace std;
const long long maxn=100000;
long long add[maxn<<2],sum[maxn<<2],add2[maxn<<2];
long long n,m;
long long a[maxn];
long long mod;
inline void Pushup(long long rt){
    (sum[rt]=(sum[rt<<1]+sum[rt<<1|1]))%mod;
}

inline void Build(long long l,long long r,long long rt){
    add[rt]=0;
        add2[rt]=1;
     if(l==r){
    sum[rt]=a[l];
    return ;
     }
     long long m=(l+r)>>1;
     Build(l,m,rt<<1);
     Build(m+1,r,rt<<1|1);
     Pushup(rt);
}

inline void Pushdown(long long rt,long long ln,long long rn){
    if(add[rt] || add2[rt]!=1){
    add2[rt<<1]*=add2[rt]%mod;
    add2[rt<<1|1]*=add2[rt]%mod;
    add[rt<<1]*=add2[rt]%mod;
    add[rt<<1|1]*=add2[rt]%mod;
    sum[rt<<1]*=add2[rt]%mod;
    sum[rt<<1|1]*=add2[rt]%mod;
    add2[rt]=1;
    (add[rt<<1]+=add[rt])%mod;
    (add[rt<<1|1]+=add[rt])%mod;
    (sum[rt<<1]+=add[rt]*ln)%mod;
    (sum[rt<<1|1]+=add[rt]*rn)%mod;
    add[rt]=0;
    }
}

inline void Update(long long L,long long R,long long C,long long l,long long r,long long rt){
     if(L<=l && r<=R){
    (sum[rt]+=C*(r-l+1))%mod;
    (add[rt]+=C)%mod;
    return ;
     }
     long long m=(l+r)>>1;
     Pushdown(rt,m-l+1,r-m);
     if(L<=m)Update(L,R,C,l,m,rt<<1);
     if(R>m)Update(L,R,C,m+1,r,rt<<1|1);
     Pushup(rt);
}

inline void Update2(long long L,long long R,long long C,long long l,long long r,long long rt){
     if(L<=l && r<=R){
    (sum[rt]*=C)%mod;
    (add[rt]*=C)%mod;
    (add2[rt]*=C)%mod;
    return ;
     }
     long long m=(l+r)>>1;
     Pushdown(rt,m-l+1,r-m);
     if(L<=m)Update2(L,R,C,l,m,rt<<1);
     if(R>m)Update2(L,R,C,m+1,r,rt<<1|1);
     Pushup(rt);
}

inline long long Query(long long L,long long R,long long l,long long r,long long rt){

    if(L<=l && r<=R){
    return sum[rt]%mod;
    }

    long long m=(l+r)>>1;
    long long ans=0;
    Pushdown(rt,m-l+1,r-m);
    if(L<=m)ans+=Query(L,R,l,m,rt<<1);
    if(R>m)ans+=Query(L,R,m+1,r,rt<<1|1);
    return ans;
}

int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);

   cin>>n>>m>>mod;

   long long x,y,z,e,f;

   for(register long long i=1;i<=n;i++){
        cin>>a[i];
   }

   Build(1,n,1);

   for(register long long i=1;i<=m;i++){
    long long k;
    cin>>k;
    if(k==1){
      cin>>x>>y>>z;
      Update2(x,y,z,1,n,1);
    }
    else if(k==2){
      cin>>x>>y>>z;
      Update(x,y,z,1,n,1);
    }
    else if(k==3){
        cin>>e>>f;
     long long Ans=Query(e,f,1,n,1);
      cout<<Ans%mod;
      cout<<endl;
    }
   }
   return 0;
}
@Andykpa 2018-03-13 22:57 回复
#include <iostream>
#include <cmath>
using namespace std;
const long long maxn=100000;
long long add[maxn<<2],sum[maxn<<2],add2[maxn<<2];
long long n,m;
long long a[maxn];
long long mod;
inline void Pushup(long long rt){
    (sum[rt]=(sum[rt<<1]+sum[rt<<1|1]))%mod;
}

inline void Build(long long l,long long r,long long rt){
    add[rt]=0;
        add2[rt]=1;
     if(l==r){
    sum[rt]=a[l];
    return ;
     }
     long long m=(l+r)>>1;
     Build(l,m,rt<<1);
     Build(m+1,r,rt<<1|1);
     Pushup(rt);
}

inline void Pushdown(long long rt,long long ln,long long rn){
    if(add[rt] || add2[rt]!=1){
    add2[rt<<1]*=add2[rt]%mod;
    add2[rt<<1|1]*=add2[rt]%mod;
    add[rt<<1]*=add2[rt]%mod;
    add[rt<<1|1]*=add2[rt]%mod;
    sum[rt<<1]*=add2[rt]%mod;
    sum[rt<<1|1]*=add2[rt]%mod;
    add2[rt]=1;
    (add[rt<<1]+=add[rt])%mod;
    (add[rt<<1|1]+=add[rt])%mod;
    (sum[rt<<1]+=add[rt]*ln)%mod;
    (sum[rt<<1|1]+=add[rt]*rn)%mod;
    add[rt]=0;
    }
}

inline void Update(long long L,long long R,long long C,long long l,long long r,long long rt){
     if(L<=l && r<=R){
    (sum[rt]+=C*(r-l+1))%mod;
    (add[rt]+=C)%mod;
    return ;
     }
     long long m=(l+r)>>1;
     Pushdown(rt,m-l+1,r-m);
     if(L<=m)Update(L,R,C,l,m,rt<<1);
     if(R>m)Update(L,R,C,m+1,r,rt<<1|1);
     Pushup(rt);
}

inline void Update2(long long L,long long R,long long C,long long l,long long r,long long rt){
     if(L<=l && r<=R){
    (sum[rt]*=C)%mod;
    (add[rt]*=C)%mod;
    (add2[rt]*=C)%mod;
    return ;
     }
     long long m=(l+r)>>1;
     Pushdown(rt,m-l+1,r-m);
     if(L<=m)Update2(L,R,C,l,m,rt<<1);
     if(R>m)Update2(L,R,C,m+1,r,rt<<1|1);
     Pushup(rt);
}

inline long long Query(long long L,long long R,long long l,long long r,long long rt){

    if(L<=l && r<=R){
    return sum[rt]%mod;
    }

    long long m=(l+r)>>1;
    long long ans=0;
    Pushdown(rt,m-l+1,r-m);
    if(L<=m)ans+=Query(L,R,l,m,rt<<1);
    if(R>m)ans+=Query(L,R,m+1,r,rt<<1|1);
    return ans;
}

int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);

   cin>>n>>m>>mod;

   long long x,y,z,e,f;

   for(register long long i=1;i<=n;i++){
        cin>>a[i];
   }

   Build(1,n,1);

   for(register long long i=1;i<=m;i++){
    long long k;
    cin>>k;
    if(k==1){
      cin>>x>>y>>z;
      Update2(x,y,z,1,n,1);
    }
    else if(k==2){
      cin>>x>>y>>z;
      Update(x,y,z,1,n,1);
    }
    else if(k==3){
        cin>>e>>f;
     long long Ans=Query(e,f,1,n,1);
      cout<<Ans%mod;
      cout<<endl;
    }
   }
   return 0;
}
@额冻豆腐 2018-03-14 00:58 回复

(a+b)mod C=a%C+b%C

乘法也如此,不能直接+= *=

@Andykpa 2018-03-14 21:27 回复

@额冻豆腐

#include <iostream>
#include <cmath>
using namespace std;
const long long maxn=100000;
long long add[maxn<<2],sum[maxn<<2],add2[maxn<<2];
long long n,m;
long long a[maxn];
long long mod;
inline void Pushup(long long rt){
    sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;
}

inline void Build(long long l,long long r,long long rt){
    add[rt]=0;
        add2[rt]=1;
     if(l==r){
    sum[rt]=a[l];
    return ;
     }
     long long m=(l+r)>>1;
     Build(l,m,rt<<1);
     Build(m+1,r,rt<<1|1);
     Pushup(rt);
}

inline void Pushdown(long long rt,long long ln,long long rn){
    if(add[rt] || add2[rt]!=1){
    add2[rt<<1]=(add2[rt<<1]*add2[rt])%mod;
    add2[rt<<1|1]=(add2[rt<<1|1]*add2[rt])%mod;
    add[rt<<1]=(add[rt<<1]*add2[rt])%mod;
    add[rt<<1|1]=(add[rt<<1]*add2[rt])%mod;
    sum[rt<<1]=(sum[rt<<1]*add2[rt])%mod;
    sum[rt<<1|1]=(sum[rt<<1|1]*add2[rt])%mod;
    add2[rt]=1;
    add[rt<<1]=(add[rt<<1]+add[rt])%mod;
    add[rt<<1|1]=(add[rt<<1|1]+add[rt])%mod;
    sum[rt<<1]=(sum[rt<<1]+add[rt]*ln)%mod;
    sum[rt<<1|1]=(sum[rt<<1|1]+add[rt]*rn)%mod;
    add[rt]=0;
    }
}

inline void Update(long long L,long long R,long long C,long long l,long long r,long long rt){
     if(L<=l && r<=R){
    sum[rt]=(sum[rt]+C*(r-l+1))%mod;
    add[rt]=(add[rt]+C)%mod;
    return ;
     }
     long long m=(l+r)>>1;
     Pushdown(rt,m-l+1,r-m);
     if(L<=m)Update(L,R,C,l,m,rt<<1);
     if(R>m)Update(L,R,C,m+1,r,rt<<1|1);
     Pushup(rt);
}

inline void Update2(long long L,long long R,long long C,long long l,long long r,long long rt){
     if(L<=l && r<=R){
    sum[rt]=(sum[rt]*C)%mod;
    add[rt]=(add[rt]*C)%mod;
    add2[rt]=(add2[rt]*C)%mod;
    return ;
     }
     long long m=(l+r)>>1;
     Pushdown(rt,m-l+1,r-m);
     if(L<=m)Update2(L,R,C,l,m,rt<<1);
     if(R>m)Update2(L,R,C,m+1,r,rt<<1|1);
     Pushup(rt);
}

inline long long Query(long long L,long long R,long long l,long long r,long long rt){

    if(L<=l && r<=R){
    return sum[rt]%mod;
    }

    long long m=(l+r)>>1;
    long long ans=0;
    Pushdown(rt,m-l+1,r-m);
    if(L<=m)ans+=Query(L,R,l,m,rt<<1);
    if(R>m)ans+=Query(L,R,m+1,r,rt<<1|1);
    return ans;
}

int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);

   cin>>n>>m>>mod;

   long long x,y,z,e,f;

   for(register long long i=1;i<=n;i++){
        cin>>a[i];
   }

   Build(1,n,1);

   for(register long long i=1;i<=m;i++){
    long long k;
    cin>>k;
    if(k==1){
      cin>>x>>y>>z;
      Update2(x,y,z,1,n,1);
    }
    else if(k==2){
      cin>>x>>y>>z;
      Update(x,y,z,1,n,1);
    }
    else if(k==3){
        cin>>e>>f;
     long long Ans=Query(e,f,1,n,1);
      cout<<Ans%mod;
      cout<<endl;
    }
   }
   return 0;
}

这样改之后 为什么我还是只有30分啊,,