怎么错的,WA or TLE
by LSY_33 @ 2023-10-19 17:17:05
@[LSY_33](/user/957873) WA
by Cockroach_hzs @ 2023-10-19 17:23:08
@[LSY_33](/user/957873) 刚又改了一下
```
#include<bits/stdc++.h>
#define lp p<<1
#define rp p<<1|1
using namespace std;
const int N=1e6+10;
long long n,a[N],mod,q,x,s,y,z;
struct tree{
int l,r,sum,mul,add;
}tr[4*N];
void up(int p){
tr[p].sum=(tr[lp].sum+tr[rp].sum)%mod;
}
void down(int p){
if(tr[p].add){
tr[lp].sum=((tr[lp].r-tr[lp].l+1)*tr[p].add%mod+tr[lp].sum*tr[p].mul)%mod;
tr[rp].sum=((tr[rp].r-tr[rp].l+1)*tr[p].add%mod+tr[rp].sum*tr[p].mul)%mod;
tr[lp].mul=tr[lp].mul*tr[p].mul%mod;
tr[rp].mul=tr[rp].mul*tr[p].mul%mod;
tr[rp].add=(tr[rp].add*tr[p].mul+tr[p].add)%mod;
tr[lp].add=(tr[lp].add*tr[p].mul+tr[p].add)%mod;
tr[p].mul=1;
tr[p].add=0;
}
}
void build(int l,int r,int p){
tr[p]={l,r,0,1,0};
if(l==r){
tr[p].sum=a[p];
return;
}
int m=(l+r)>>1;
build(l,m,lp);
build(m+1,r,rp);
up(p);
}
void cheng(int l,int r,int k,int p){
if(tr[p].l<l||tr[p].r>r){
return ;
}
if(tr[p].l>=l&&tr[p].r<=r){
tr[p].mul*=k;
tr[p].add*=k;
tr[p].sum*=k;
return;
}
int m=(tr[p].l+tr[p].r)>>1;
down(p);
if(x<=m){
cheng(l,r,k,lp);
}
if(y>m){
cheng(l,r,k,rp);
}
up(p);
}
void jia(int l,int r,int k,int p){
if(tr[p].l<l||tr[p].r>r){
return ;
}
if(tr[p].l>=l&&tr[p].r<=r){
tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
tr[p].add+=k;
return;
}
int m=(tr[p].l+tr[p].r)>>1;
down(p);
if(x<=m){
jia(l,r,k,lp);
}
if(y>m){
jia(l,r,k,rp);
}
up(p);
}
int shu(int x,int y,int p){
if(x<=tr[p].l&&y>=tr[p].r){
return tr[p].sum;
}
int m=tr[p].l+tr[p].r>>1;
int cnt=0;
if(x<=m){
cnt+=shu(x,y,lp);
}
if(y>m){
cnt+=shu(x,y,rp);
}
return cnt;
}
int main(){
cin>>n>>q>>mod;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1);
for(int i=1;i<=q;i++){
cin>>s;
if(s==1){
cin>>x>>y>>z;
cheng(x,y,z,1);
}
if(s==2){
cin>>x>>y>>z;
jia(x,y,z,1);
}
if(s==3){
cin>>x>>y;
cout<<shu(x,y,1)%mod<<endl;
}
}
return 0;
}
```
by Cockroach_hzs @ 2023-10-19 17:24:00
jia()里没%
by LSY_33 @ 2023-10-19 17:29:47
@[LSY_33](/user/957873) 这样吗
```
#include<bits/stdc++.h>
#define lp p<<1
#define rp p<<1|1
using namespace std;
const int N=1e6+10;
long long n,a[N],mod,q,x,s,y,z;
struct tree{
int l,r,sum,mul,add;
}tr[4*N];
void up(int p){
tr[p].sum=(tr[lp].sum+tr[rp].sum)%mod;
}
void down(int p){
if(tr[p].add){
tr[lp].sum=((tr[lp].r-tr[lp].l+1)*tr[p].add%mod+tr[lp].sum*tr[p].mul)%mod;
tr[rp].sum=((tr[rp].r-tr[rp].l+1)*tr[p].add%mod+tr[rp].sum*tr[p].mul)%mod;
tr[lp].mul=tr[lp].mul*tr[p].mul%mod;
tr[rp].mul=tr[rp].mul*tr[p].mul%mod;
tr[rp].add=(tr[rp].add*tr[p].mul+tr[p].add)%mod;
tr[lp].add=(tr[lp].add*tr[p].mul+tr[p].add)%mod;
tr[p].mul=1;
tr[p].add=0;
}
}
void build(int l,int r,int p){
tr[p]={l,r,0,1,0};
if(l==r){
tr[p].sum=a[p];
return;
}
int m=(l+r)>>1;
build(l,m,lp);
build(m+1,r,rp);
up(p);
}
void cheng(int l,int r,int k,int p){
if(tr[p].l<l||tr[p].r>r){
return ;
}
if(tr[p].l>=l&&tr[p].r<=r){
tr[p].mul=tr[p].mul*k%mod;
tr[p].add=tr[p].add*k%mod;
tr[p].sum=tr[p].sum*k%mod;
return;
}
int m=(tr[p].l+tr[p].r)>>1;
down(p);
if(x<=m){
cheng(l,r,k,lp);
}
if(y>m){
cheng(l,r,k,rp);
}
up(p);
}
void jia(int l,int r,int k,int p){
if(tr[p].l<l||tr[p].r>r){
return ;
}
if(tr[p].l>=l&&tr[p].r<=r){
tr[p].sum=(tr[p].sum+(tr[p].r-tr[p].l+1)*k)%mod;
tr[p].add=(tr[p].add+k)%mod;
return;
}
int m=(tr[p].l+tr[p].r)>>1;
down(p);
if(x<=m){
jia(l,r,k,lp);
}
if(y>m){
jia(l,r,k,rp);
}
up(p);
}
int shu(int x,int y,int p){
if(x<=tr[p].l&&y>=tr[p].r){
return tr[p].sum;
}
int m=tr[p].l+tr[p].r>>1;
int cnt=0;
if(x<=m){
cnt+=shu(x,y,lp);
}
if(y>m){
cnt+=shu(x,y,rp);
}
return cnt;
}
int main(){
cin>>n>>q>>mod;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1);
for(int i=1;i<=q;i++){
cin>>s;
if(s==1){
cin>>x>>y>>z;
cheng(x,y,z,1);
}
if(s==2){
cin>>x>>y>>z;
jia(x,y,z,1);
}
if(s==3){
cin>>x>>y;
cout<<shu(x,y,1)%mod<<endl;
}
}
return 0;
}
```
by Cockroach_hzs @ 2023-10-19 17:35:11
`down()` 里应该这么判断下放条件:
```cpp
if(tr[p].add || tr[p].add != 1){
```
因为有时候会出现没有 $add$ 标记只有 $mul$ 标记的情况,而这时同样需要下放。
而且 `shu()` 里统计答案的
```cpp
if(x<=m){
cnt+=shu(x,y,lp);
}
if(y>m){
cnt+=shu(x,y,rp);
}
```
没 %
目前就看出来这么多
by LSY_33 @ 2023-10-19 17:58:36
@[LSY_33](/user/957873)
谢谢orz ~~虽然还是没过~~ 不过还是我个人原因了
by Cockroach_hzs @ 2023-10-19 21:00:45
@[Cockroach_hzs](/user/730894) 拜拜,我要出发去打 CSP-J 了。RP++
by LSY_33 @ 2023-10-20 06:13:50
@[LSY_33](/user/957873)
加油 我也要去打了 ~~s组啥也不会等s了~~
rp++!
by Cockroach_hzs @ 2023-10-20 18:34:21