您好,在函数pushdown中,建议将
```
tr[k*2].data_sum=(tr[k*2].data_sum+add_tag[k])%p;
tr[k*2+1].data_sum=(tr[k*2+1].data_sum+add_tag[k])%p;
```
修改为
```
tr[k*2].data_sum=(tr[k*2].data_sum+add_tag[k]*(tr[k*2].r-tr[k*2].l+1)%p)%p;
tr[k*2+1].data_sum=(tr[k*2+1].data_sum+add_tag[k]*(tr[k*2+1].r-tr[k*2+1].l+1)%p)%p;
```
addtag的下放是对于下面部分的每一个数的,所以您要乘上区间长度。
~~另外您的码风挺抽象的~~
下面是AC代码
```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5;
struct tree {
ll l,r,data_sum;
}tr[4*N+5];
ll n,p,a[N+5],m,op,t,g,c,mul_tag[4*N+5],add_tag[4*N+5],ans;
inline void build(ll l1,ll r1,ll k) {
tr[k].l=l1;
tr[k].r=r1;
if(l1==r1) {
tr[k].data_sum=a[l1]%p;
return;
}
ll mid=(r1-l1)/2+l1;
build(l1,mid,k*2);
build(mid+1,r1,k*2+1);
tr[k].data_sum=(tr[k*2].data_sum+tr[k*2+1].data_sum)%p;
}
inline void pushdown(ll k) {
tr[k*2].data_sum=(tr[k*2].data_sum*mul_tag[k])%p;
tr[k*2].data_sum=(tr[k*2].data_sum+add_tag[k]*(tr[k*2].r-tr[k*2].l+1)%p)%p;
mul_tag[k*2]=(mul_tag[k*2]*mul_tag[k])%p;
add_tag[k*2]=(add_tag[k*2]*mul_tag[k])%p;
add_tag[k*2]=(add_tag[k*2]+add_tag[k])%p;
tr[k*2+1].data_sum=(tr[k*2+1].data_sum*mul_tag[k])%p;
tr[k*2+1].data_sum=(tr[k*2+1].data_sum+add_tag[k]*(tr[k*2+1].r-tr[k*2+1].l+1)%p)%p;
mul_tag[k*2+1]=(mul_tag[k*2+1]*mul_tag[k])%p;
add_tag[k*2+1]=(add_tag[k*2+1]*mul_tag[k])%p;
add_tag[k*2+1]=(add_tag[k*2+1]+add_tag[k])%p;
mul_tag[k]=1;
add_tag[k]=0;
}
inline void mul(ll k,ll l1,ll r1) {
if(tr[k].l>=l1&&tr[k].r<=r1) {
tr[k].data_sum=(tr[k].data_sum*c)%p;
mul_tag[k]=(mul_tag[k]*c)%p;
add_tag[k]=(add_tag[k]*c)%p;
return;
}
pushdown(k);
ll mid=(tr[k].r-tr[k].l)/2+tr[k].l;
if(t<=mid)
mul(k*2,l1,r1);
if(g>mid)
mul(k*2+1,l1,r1);
tr[k].data_sum=(tr[k*2].data_sum+tr[k*2+1].data_sum)%p;
}
inline void add(ll k,ll l1,ll r1) {
if(tr[k].l>=l1&&tr[k].r<=r1) {
tr[k].data_sum=(tr[k].data_sum+((tr[k].r-tr[k].l+1)*c)%p)%p;
add_tag[k]=(add_tag[k]+c)%p;
return;
}
pushdown(k);
ll mid=(tr[k].r-tr[k].l)/2+tr[k].l;
if(t<=mid)
add(k*2,l1,r1);
if(g>mid)
add(k*2+1,l1,r1);
tr[k].data_sum=(tr[k*2].data_sum+tr[k*2+1].data_sum)%p;
}
inline void query(ll k,ll l1,ll r1) {
if(tr[k].l>=l1&&tr[k].r<=r1) {
ans=(ans+tr[k].data_sum)%p;
return;
}
pushdown(k);
ll mid=(tr[k].r-tr[k].l)/2+tr[k].l;
if(t<=mid)
query(k*2,l1,r1);
if(g>mid)
query(k*2+1,l1,r1);
tr[k].data_sum=(tr[k*2].data_sum+tr[k*2+1].data_sum)%p;
}
int main() {
scanf("%lld%lld",&n,&p);
for(int i=1; i<=n; i++)
scanf("%lld",&a[i]);
build(1,n,1);
scanf("%lld",&m);
for(int i=0; i<4*N+5; i++)
mul_tag[i]=1;
for(int i=1; i<=m; i++) {
scanf("%lld%lld%lld",&op,&t,&g);
if(op==1) {
scanf("%lld",&c);
mul(1,t,g);
} else if(op==2) {
scanf("%lld",&c);
add(1,t,g);
} else {
ans=0;
query(1,t,g);
printf("%lld\n",ans);
}
}
return 0;
}
```
by flywatre @ 2023-05-04 08:16:07
谢谢,孩子今年初一,今天上学了,自学了快一年,除了在网上查找一些资料和给他买了基本书籍以外就在网上刷题,因为这道题昨晚3点没有睡,感谢大神指点,等放学了让他看看,希望能与您取得联系,当孩子指导老师,不胜感激!
by jjh20100730 @ 2023-05-04 08:52:18
@[jjh20100730](/user/812955) emmm本人也是在读高中学生,有什么问题可以直接私信问我,我有时间的话会解答的。直接在网上问大概也是有人会回答的。然后这是我qq:707980965
by flywatre @ 2023-05-04 11:18:35
@[jjh20100730](/user/812955) 后排%拜
by PorkSausage @ 2024-04-22 23:16:05