lz能不能说一说每个变量的用途,看不懂。。。
@[shalu](/user/920861)
by Trump_ @ 2023-08-06 14:51:24
@[Trump_](/user/539200)
已注释,贴代码
------------
```cpp
/*
函数注释:
k:当前结点
l:左端点
r:右端点
x:区间修改的左结点
y:区间修改的右结点
z:区间修改的值(乘或加)
s:区间查询的起点
t: 区间查询的终点
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int n,q,m,tmp[MAXN],f[MAXN<<2],v1[MAXN<<2],v2[MAXN<<2];//两个懒标记
inline void buildtree(int k,int l,int r){//建树
v2[k]=1;
if(l==r){
f[k]=tmp[l]%m;
return ;
}
int mid=(l+r)>>1;
buildtree(k+k,l,mid);
buildtree(k+k+1,mid+1,r);
f[k]=(f[k+k]+f[k+k+1])%m;
}
inline void add(int k,int l,int r,int x,int y,int z){//区间加
if(l==x&&r==y){
v1[k]=(v1[k]+z)%m;
return ;
}
v2[k+k]=(v2[k+k]*v2[k])%m,v2[k+k+1]=(v2[k+k+1]*v2[k])%m,v2[k]=1;// 标记下传
v1[k+k]=(v1[k+k]+v1[k])%m,v1[k+k+1]=(v1[k+k+1]+v1[k])%m,v1[k]=0;// 标记下传
int mid=(l+r)>>1;
if(y<=mid){
add(k+k,l,mid,x,y,z);
}
else{
if(x>mid){
add(k+k+1,mid+1,r,x,y,z);
}
else{
add(k+k,l,mid,x,mid,z),add(k+k+1,mid+1,r,mid+1,y,z);
}
}
f[k]=(f[k+k]*v2[k]+v1[k+k]*(mid-l+1)+f[k+k+1]*v2[k+k+1]+v1[k+k+1]*(r-mid))%m;//修改已下传结点的值
}
inline void mul(int k,int l,int r,int x,int y,int z){
if(l==x&&r==y){
v2[k]=(v2[k]*z)%m;//这里类似一个乘法分配律
v1[k]=(v1[k]*z)%m;
return ;
}
v2[k+k]=(v2[k+k]*v2[k])%m,v2[k+k+1]=(v2[k+k+1]*v2[k])%m,v2[k]=1;// 标记下传
v1[k+k]=(v1[k+k]+v1[k])%m,v1[k+k+1]=(v1[k+k+1]+v1[k])%m,v1[k]=0;// 标记下传
int mid=(l+r)>>1;
if(y<=mid){
mul(k+k,l,mid,x,y,z);
}
else{
if(x>mid){
mul(k+k+1,mid+1,r,x,y,z);
}
else{
mul(k+k,l,mid,x,mid,z),mul(k+k+1,mid+1,r,mid+1,y,z);
}
}
f[k]=(f[k+k]*v2[k]+v1[k+k]*(mid-l+1)+f[k+k+1]*v2[k+k+1]+v1[k+k+1]*(r-mid))%m;//修改已下传结点的值
}
int calc(int k,int l,int r,int s,int t){
if(l==s&&r==t){
return (f[k]*v2[k]+v1[k]*(r-l+1))%m;
}
v2[k+k]=(v2[k+k]*v2[k])%m,v2[k+k+1]=(v2[k+k+1]*v2[k])%m,v2[k]=1;// 标记下传
v1[k+k]=(v1[k+k]+v1[k])%m,v1[k+k+1]=(v1[k+k+1]+v1[k])%m,v1[k]=0;// 标记下传
int mid=(l+r)>>1,res=0;
if(t<=mid){
res=calc(k+k,l,mid,s,t)%m;
}
else{
if(s>mid){
res=calc(k+k+1,mid+1,r,s,t)%m;
}
else{
res=(calc(k+k,l,mid,s,mid)%m+calc(k+k+1,mid+1,r,mid+1,t)%m)%m;
}
}
f[k]=(f[k+k]*v2[k]+v1[k+k]*(mid-l+1)+f[k+k+1]*v2[k+k+1]+v1[k+k+1]*(r-mid))%m;//修改已下传结点的值
return res;
}
signed main(){
std::ios::sync_with_stdio(false);//加速
cin>>n>>q>>m;//后面是读入就不解释了
for(int i=1;i<=n;i++){
cin>>tmp[i];
}
buildtree(1,1,n);
for(int i=1;i<=q;i++){
int op,x,y,k;
cin>>op>>x>>y;
if(op==1){
cin>>k;
mul(1,1,n,x,y,k);
}
else if(op==2){
cin>>k;
add(1,1,n,x,y,k);
}
else{
cout<<calc(1,1,n,x,y)%m<<endl;
}
}
return 0;
}
```
by shalu @ 2023-08-06 16:07:15
@[Trump_](/user/539200)
求大佬修改
QAQ
by shalu @ 2023-08-06 16:09:42
@[shalu](/user/920861) 我康康奥,但不要抱太大希望,毕竟我也菜QAQ
by Trump_ @ 2023-08-06 16:20:07
@[Trump_](/user/539200)
感谢
by shalu @ 2023-08-06 16:21:57
@[shalu](/user/920861) pushdown是不是写错了,我个人感觉加法的懒标记会被新的乘法懒标记改变,乘法同理也会被加法改变。
by Trump_ @ 2023-08-06 16:29:27
@[Trump_](/user/539200)
好的,我憋了一天半了
by shalu @ 2023-08-06 16:31:49
奥,我没傻,就是这样的
by Trump_ @ 2023-08-06 16:33:38
@[Trump_](/user/539200)
那该怎么改?本人ju ruo
by shalu @ 2023-08-06 16:37:10
@[shalu](/user/920861) 抱歉抱歉,我刚才说错了QAQ,实际上加法不会对乘法造成影响,但乘法会对加法造成影响
by Trump_ @ 2023-08-06 16:37:30