@[_buzhidao_](/user/917775) 你的spread对tag的下放好像有问题，如果遇到乘法操作，那么区间内的加法标记也是要乘的
好比同一个区间加上五再乘以三，那么加法标记应修改为十五，还要注意乘法和加法的操作顺序。。
by HeYilin @ 2024-04-10 07:06:58
@[HeYilin](/user/728459) 这么说 `upd2` 也有类似的问题。。。
by _buzhidao_ @ 2024-04-10 19:45:58
@[HeYilin](/user/728459) 改成了这个样子：
```cpp
if(t[p].tag2){
tmp=t[p].tag2;
t[p*2].va=(t[p*2].va*tmp)%m;
t[p*2+1].va=(t[p*2+1].va*tmp)%m;
t[p*2].tag2=(t[p*2].tag2*tmp)%m;t[p*2+1].tag2=(t[p*2+1].tag2*tmp)%m;
t[p*2].tag1=(t[p*2].tag1*tmp)%m;t[p*2+1].tag1=(t[p*2+1].tag1*tmp)%m;//here
t[p].tag2=0;
}
```
```cpp
void upd2(int p,int l,int r,int k){//bug
if(t[p].l>=l&&t[p].r<=r){
t[p].va=(t[p].va*k)%m;
t[p].tag2=(t[p].tag2*k)%m;
t[p].tag1=(t[p].tag1*k)%m;//here
return;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) upd2(p*2,l,r,k);
if(r>mid) upd2(p*2+1,l,r,k);
t[p].va=(t[p*2].va+t[p*2+1].va)%m;
}
```
自测#1不通过，继续求助orz
by _buzhidao_ @ 2024-04-10 19:49:55
@[_buzhidao_](/user/917775) 我有点忍不住想爆粗口。。这么说吧，如果你的tag2是乘法标记，那么你应该把不需要处理的状态标记成1而不是0，因为虽然你这样标记处理好像也没问题（？，但是如果数据给你的全是乘1那么你的代码执行效率会大大降低；其次如果标成1的话，需要在建树的时候标记；处理懒标记，下放时要先干数值，再干乘法，最后做加法标记，这样加法标记不会漏乘：想一想，如果乘法的懒标记还没有下放，就用没下放的乘法标记修改加法，那么父节点应该下放的那个数就少乘了，自然就不对
by HeYilin @ 2024-04-10 22:19:04
我这里放一下我的代码，里面乘法对应tag1，加法对应tag2，你可以对照看一下，注意一下初始化和标记，我现在不太方便调试你的代码（qwq
```cpp
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int maxn=1e5+10;
ll n,mod,q,a[maxn],op,x,y,k;
struct SegmentTree{
ll l,r;
ll sum;
ll tag1=1,tag2;
}t[maxn<<2];
void build(ll p,ll l,ll r){
t[p].l=l,t[p].r=r;
if(l==r){t[p].sum=a[l]%mod;return;}
ll mid=l+r>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
void pushdown(ll p){
//sum
t[p*2].sum*=t[p].tag1;t[p*2].sum%=mod;
t[p*2].sum+=t[p].tag2*(t[p*2].r-t[p*2].l+1);t[p*2].sum%=mod;
t[p*2+1].sum*=t[p].tag1;t[p*2+1].sum%=mod;
t[p*2+1].sum+=t[p].tag2*(t[p*2+1].r-t[p*2+1].l+1);t[p*2+1].sum%=mod;
//tag1
t[p*2].tag1*=t[p].tag1;t[p*2].tag1%=mod;
t[p*2+1].tag1*=t[p].tag1;t[p*2+1].tag1%=mod;
//tag2
t[p*2].tag2*=t[p].tag1;t[p*2].tag2%=mod;
t[p*2].tag2+=t[p].tag2;t[p*2].tag2%=mod;
t[p*2+1].tag2*=t[p].tag1;t[p*2+1].tag2%=mod;
t[p*2+1].tag2+=t[p].tag2;t[p*2+1].tag2%=mod;
//t[p]
t[p].tag1=1,t[p].tag2=0;
}
void change1(ll p,ll l,ll r,ll d){// * x
if(l<=t[p].l&&r>=t[p].r){
t[p].sum*=d;t[p].sum%=mod;
t[p].tag1*=d;t[p].tag1%=mod;
t[p].tag2*=d;t[p].tag2%=mod;//
return;
}
pushdown(p);
ll mid=t[p].l+t[p].r>>1;
if(l<=mid)change1(p*2,l,r,d);
if(r>mid)change1(p*2+1,l,r,d);
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
void change2(ll p,ll l,ll r,ll d){// + x
if(l<=t[p].l&&r>=t[p].r){
t[p].sum+=d*(t[p].r-t[p].l+1);t[p].sum%=mod;
t[p].tag2+=d;t[p].tag2%=mod;
return;
}
pushdown(p);
ll mid=t[p].l+t[p].r>>1;
if(l<=mid)change2(p*2,l,r,d);
if(r>mid)change2(p*2+1,l,r,d);
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
ll query(ll p,ll l,ll r){
if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
pushdown(p);
ll mid=t[p].l+t[p].r>>1;
ll val=0;
if(l<=mid)val+=query(p*2,l,r);
if(r>mid)val+=query(p*2+1,l,r);
return val%mod;
}
int main(){
cin>>n>>q>>mod;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(q--){
cin>>op>>x>>y;
if(op==1){
cin>>k;
change1(1,x,y,k);
}
if(op==2){
cin>>k;
change2(1,x,y,k);
}
if(op==3)cout<<query(1,x,y)<<"\n";
}
return 0;
}
/*
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
*/
```
by HeYilin @ 2024-04-10 22:22:26
@[HeYilin](/user/728459) 没错，我判断 `tag2==0` 其实是个bug，您的指导我明天再精读orz%%%
by _buzhidao_ @ 2024-04-10 22:46:04
@[HeYilin](/user/728459) 改成了这个样子
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define read(x) cin>>x
template<typename T>inline void read(T &x){
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=f;
}
int n,q,m,a,b,c,d;ll s[(int)4e5];
struct tree{
int l,r;ll va,tag1,tag2;
} t[(int)4e5+5];
void buildt(int p,int l,int r){
t[p].l=l,t[p].r=r;t[p].tag2=1;
if(l==r){
t[p].va=s[l]%m;return;
}
int mid=(l+r)>>1;
buildt(p*2,l,mid);
buildt(p*2+1,mid+1,r);
t[p].va=(t[p*2].va+t[p*2+1].va)%m;
}
void spread(int p){//
ll tmp1=t[p].tag1,tmp2=t[p].tag2;
//va
t[p*2].va=(t[p*2].va*tmp2)%m;
t[p*2+1].va=(t[p*2+1].va*tmp2)%m;
t[p*2].va=(t[p*2].va+tmp1*(t[p*2].r-t[p*2].l+1))%m;
t[p*2+1].va=(t[p*2+1].va+tmp1*(t[p*2+1].r-t[p*2+1].l+1))%m;
//tag2
t[p*2].tag2=(t[p*2].tag2*tmp2)%m;t[p*2+1].tag2=(t[p*2+1].tag2*tmp2)%m;
//tag1
t[p*2].tag1=(t[p*2].tag1+tmp1)%m;t[p*2+1].tag1=(t[p*2+1].tag1+tmp1)%m;
t[p*2].tag1=(t[p*2].tag1*tmp2)%m;t[p*2+1].tag1=(t[p*2+1].tag1*tmp2)%m;
//t[p]
t[p].tag1=0;t[p].tag2=1;
}
void upd1(int p,int l,int r,int k){
if(t[p].l>=l&&t[p].r<=r){
t[p].va=(t[p].va+(ll)k*(t[p].r-t[p].l+1))%m;
t[p].tag1=(t[p].tag1+k)%m;
return;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) upd1(p*2,l,r,k);
if(r>mid) upd1(p*2+1,l,r,k);
t[p].va=(t[p*2].va+t[p*2+1].va)%m;
}
void upd2(int p,int l,int r,int k){
if(t[p].l>=l&&t[p].r<=r){
t[p].va=(t[p].va*k)%m;
t[p].tag2=(t[p].tag2*k)%m;
t[p].tag1=(t[p].tag1*k)%m;
return;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) upd2(p*2,l,r,k);
if(r>mid) upd2(p*2+1,l,r,k);
t[p].va=(t[p*2].va+t[p*2+1].va)%m;
}
ll query(int p,int l,int r){
if(l<=t[p].l&&r>=t[p].r){/*cout<<t[p].l<<t[p].r<<' ';*/return t[p].va;}
spread(p);
int mid=(t[p].l+t[p].r)>>1;ll ans=0;
if(l<=mid) ans+=query(p*2,l,r);
if(r>mid) ans+=query(p*2+1,l,r);
return ans%m;
}
int main(){
read(n);read(q);read(m);
for(int i=1;i<=n;++i) read(s[i]);
buildt(1,1,n);
for(int i=0;i<q;++i){
read(a);
if(a==1){
read(b);read(c);read(d);
upd2(1,b,c,d%m);
}
else if(a==2){
read(b);read(c);read(d);
upd1(1,b,c,d%m);
}
else if(a==3){
read(b);read(c);
cout<<query(1,b,c)<<endl;
}
//if(i==1) for(int i=1;i<=4*n;++i) if(t[i].va!=0) cout<<t[i].va<<' '<<t[i].l<<' '<<t[i].r<<endl;
/*for(int i=1;i<=n;++i){
cout<<query(1,i,i)<<' ';
}cout<<endl;*/
}
return 0;
}
```
by _buzhidao_ @ 2024-04-12 06:49:34
@[HeYilin](/user/728459) 0，但是每个点前一两行能过
by _buzhidao_ @ 2024-04-12 06:59:15
@[_buzhidao_](/user/917775) 下放加法的问题。可以看一下我的代码。如果是保证每次修改都将加法操作的标记乘上乘法标记，那么下放时当前节点的加法标记应该是先先乘后加，因为加法的标记已经先处理过了，乘完乘法标记了，所以先加在乘的话，加法标记的数值是被乘了两遍的，具体的好像改一下顺序就可以。
by HeYilin @ 2024-04-12 07:06:37
@[_buzhidao_](/user/917775) 也就是你spread中tag1的那两行
by HeYilin @ 2024-04-12 07:09:26