建议大佬学完线段树再来问问吧
by 羊羊君的幻想 @ 2023-09-17 11:18:47
先学分块再学线段树（？）%%%
by 羊羊君的幻想 @ 2023-09-17 11:21:14
```cpp
#include<bits/stdc++.h>
#define ll long long
#define N 100009
using namespace std;
ll a[N],b[N],c[N],d[N],e[N],q;
ll n,m,L;
void add(ll l,ll r,ll z){
ll p=min(r,b[l]*L);
for(ll i=l;i<=p;i++)a[i]+=z;
if(b[l]!=b[r])
for(ll i=b[r]*L-L+1;i<=r;i++)a[i]+=z,e[b[i]]+=z;
for(int k=b[l]+1;k<=b[r]-1;k++)c[k]+=z;
}
void mul(ll l,ll r,ll z){
ll p=min(r,b[l]*L);
for(ll i=l;i<=p;i++)a[i]*=z;
if(b[l]!=b[r])
for(ll i=b[r]*L-L+1;i<=r;i++)a[i]*=z,e[b[i]]+=(z-1)*a[i];
for(int k=b[l]+1;k<=b[r]-1;k++)c[k]*=z;
for(int k=b[l]+1;k<=b[r]-1;k++)d[k]*=z;
}
ll rsq(ll l,ll r){
ll s=0;
if(b[l]==b[r])
for(ll i=l;i<=r;i++)s=(s+a[i]*d[b[i]]+c[b[i]])%q;
else{
for(ll i=l;b[i]==b[l];i++)s=(s+a[i]*d[b[i]]+c[b[i]])%q;
for(ll i=r;b[i]==b[r];i--)s=(s+a[i]*d[b[i]]+c[b[i]])%q;
// cout<<"s1:"<<s<<endl;
for(ll k=b[l]+1;k<=b[r]-1;k++){s=(s+e[k]*d[k]+c[k]*L)%q;}//cout<<"for:"<<e[k]<<" "<<d[k]<<" "<<c[k]<<" "<<L<<endl;
// cout<<"s2:"<<s<<endl;
}
return s;
}
int main(){
cin>>n>>m>>q;
L=sqrt(n);
for(ll i=1;i<=n;i++)cin>>a[i];
for(ll i=1;i<=n;i++)b[i]=(i-1)/L+1;
for(ll i=1;i<=n;i++)d[i]=1;
for(ll i=1;i<=n;i++)e[b[i]]+=a[i];
// for(ll i=1;i<=L+2;i++)cout<<e[i]<<" ";cout<<endl<<endl;
for(ll i=1;i<=m;i++){
ll t,x,y,z;
cin>>t;
if(t==1){cin>>x>>y>>z;mul(x,y,z);}
else if(t==2){cin>>x>>y>>z;add(x,y,z);}
else{cin>>x>>y;cout<<rsq(x,y)%q<<endl;}
// cout<<"arr:";for(ll i=1;i<=n;i++)cout<<a[i]*d[b[i]]+c[b[i]]<<" ";cout<<endl;
// cout<<"a:";for(ll i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;
// cout<<"c:";for(ll i=1;i<=b[n];i++)cout<<c[i]<<" ";cout<<endl;
// cout<<"d:";for(ll i=1;i<=b[n];i++)cout<<d[i]<<" ";cout<<endl;
}
return 0;
}
```
改了一下，能过样例了，但是全WA
by asas111 @ 2023-09-17 14:11:21
```
#include<bits/stdc++.h>
#define ll long long
#define m 571373
#define N 100009
using namespace std;
ll n,q,_,L,a[N],b[N],bs[N],c[N],d[N];
void mul(ll x,ll y,ll k){
if(b[x]==b[y])
for(ll i=x;i<=y;i++)bs[b[i]]=(bs[b[i]]+a[i]*(k-1))%m,a[i]=(a[i]*k)%m;
else{
for(ll i=b[x]+1;i<=b[y]-1;i++)c[i]=(c[i]*k)%m,d[i]=(d[i]*k)%m;
// for(ll i=x;b[i]==b[x];i++)bs[b[i]]=(bs[b[i]]+a[i]*(k-1))%m,a[i]=(a[i]*k)%m;
// for(ll i=y;b[i]==b[y];i--)bs[b[i]]=(bs[b[i]]+a[i]*(k-1))%m,a[i]=(a[i]*k)%m;
bs[b[x]]=bs[b[y]]=0;
for(ll i=(b[x]-1)*L+1;i<=min(n,b[x]*L);i++)a[i]=((a[i]*c[b[i]]+d[b[i]])*(i<x?1:k))%m,bs[b[i]]=(bs[b[i]]+a[i])%m;d[b[x]]=0,c[b[x]]=1;
for(ll i=(b[y]-1)*L+1;i<=min(n,b[y]*L);i++)a[i]=((a[i]*c[b[i]]+d[b[i]])*(i>y?1:k))%m,bs[b[i]]=(bs[b[i]]+a[i])%m;d[b[y]]=0,c[b[y]]=1;
}
}
void add(ll x,ll y,ll k){
if(b[x]==b[y])
for(ll i=x;i<=y;i++)bs[b[i]]=(bs[b[i]]+k)%m,a[i]=(a[i]+k)%m;
else{
for(ll i=b[x]+1;i<=b[y]-1;i++)d[i]=(d[i]+k)%m;
// for(ll i=x;b[i]==b[x];i++)bs[b[i]]=(bs[b[i]]+k)%m,a[i]=(a[i]+k)%m;
// for(ll i=y;b[i]==b[y];i--)bs[b[i]]=(bs[b[i]]+k)%m,a[i]=(a[i]+k)%m;
bs[b[x]]=bs[b[y]]=0;
for(ll i=(b[x]-1)*L+1;i<=min(n,b[x]*L);i++)a[i]=(a[i]*c[b[i]]+(i<x?0:k)+d[b[i]])%m,bs[b[i]]=(bs[b[i]]+a[i])%m;d[b[x]]=0,c[b[x]]=1;
for(ll i=(b[y]-1)*L+1;i<=min(n,b[y]*L);i++)a[i]=(a[i]*c[b[i]]+(i>y?0:k)+d[b[i]])%m,bs[b[i]]=(bs[b[i]]+a[i])%m;d[b[y]]=0,c[b[y]]=1;
}
}
ll rsq(ll x,ll y){
ll s=0;
if(b[x]==b[y])
for(ll i=x;i<=y;i++)s=(s+a[i]*c[b[i]]+d[b[i]])%m;
else{
for(ll i=b[x]+1;i<=b[y]-1;i++)s=(s+(bs[i])*c[i]+d[i]*(min(n,L*b[i])-((b[i]-1)*L+1)+1))%m;
for(ll i=x;b[i]==b[x];i++)s=(s+a[i]*c[b[i]]+d[b[i]])%m;
for(ll i=y;b[i]==b[y];i--)s=(s+a[i]*c[b[i]]+d[b[i]])%m;
}
return s;
}
int main(){
cin>>n>>q>>_;
L=sqrt(n);
for(ll i=1;i<=n;i++)cin>>a[i];
for(ll i=1;i<=n;i++)b[i]=(i-1)/L+1;
for(ll i=1;i<=n;i++)bs[b[i]]=(bs[b[i]]+a[i])%m;
for(ll i=1;i<=n;i++)c[i]=1;
#ifndef ONLINE_JUDGE
for(ll i=1;i<=n;i++)cout<<i<<" a:"<<a[i]<<" b:"<<b[i]<<" bs:"<<bs[b[i]]<<"\n";
#endif
for(ll i=1;i<=q;i++){
ll op,x,y,k;
cin>>op;
if(op==1){
cin>>x>>y>>k;
mul(x,y,k);
}
else if(op==2){
cin>>x>>y>>k;
add(x,y,k);
}
else{
cin>>x>>y;
cout<<rsq(x,y)%m<<"\n";
}
#ifndef ONLINE_JUDGE
for(ll i=1;i<=n;i++)cout<<i<<" a:"<<a[i]<<" b:"<<b[i]<<" c:"<<c[b[i]]<<" d:"<<d[b[i]]<<" bs:"<<bs[b[i]]<<"\n";
#endif
}
return 0;
}
```
终于过了
by asas111 @ 2023-12-03 12:08:21