两篇代码一个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;
}