文章目录
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
D
e
s
c
r
i
p
t
i
o
n
Description
Description
S
o
l
u
t
i
o
n
Solution
Solution
C
o
d
e
Code
Code
R
e
s
u
l
t
Result
Result
H
y
p
e
r
l
i
n
k
Hyperlink
Hyperlink
https://www.luogu.com.cn/problem/P3373
D
e
s
c
r
i
p
t
i
o
n
Description
Description
写一种数据结构，要求支持区间乘，区间加，区间求和
数据范围：
n
,
m
≤
1
0
5
n,m\leq 10^5
n,m≤105
S
o
l
u
t
i
o
n
Solution
Solution
记住：每一个乘操作都会影响和操作！每一个乘操作都会影响和操作！每一个乘操作都会影响和操作！
然后
p
u
s
h
d
o
w
n
pushdown
pushdown的时候改一改就好了
时间复杂度：
O
(
(
n
+
m
)
l
o
g
n
)
O((n+m)logn)
O((n+m)logn)
C
o
d
e
Code
Code
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 100010
using namespace std
;int n
,mod
,l
,r
,opt
,m
;
LL a
[N
],x
;
struct xds
{
#define lson k<<1
#define rson k<<1|1
LL sum
[N
<<2],lzy
[N
<<2],mul
[N
<<2];
inline void build(int k
=1,int l
=1,int r
=n
)
{
mul
[k
]=1;
if(l
==r
) return (void)(sum
[k
]=a
[l
]);
int mid
=l
+r
>>1;
build(lson
,l
,mid
);build(rson
,mid
+1,r
);
return (void)(sum
[k
]=(sum
[lson
]+sum
[rson
])%mod
);
}
inline void pushdown(int k
,int l
,int r
)
{
if(lzy
[k
]==0&&mul
[k
]==1) return;
int mid
=l
+r
>>1;
sum
[lson
]=(sum
[lson
]*mul
[k
]%mod
+(mid
-l
+1)*lzy
[k
]%mod
)%mod
;
sum
[rson
]=(sum
[rson
]*mul
[k
]%mod
+(r
-mid
)*lzy
[k
]%mod
)%mod
;
mul
[lson
]=mul
[lson
]*mul
[k
]%mod
;mul
[rson
]=mul
[rson
]*mul
[k
]%mod
;
lzy
[lson
]=(lzy
[lson
]*mul
[k
]%mod
+lzy
[k
])%mod
;
lzy
[rson
]=(lzy
[rson
]*mul
[k
]%mod
+lzy
[k
])%mod
;
return(void)(mul
[k
]=1,lzy
[k
]=0);
}
inline void Modify_add(int ql
,int qr
,LL d
,int k
=1,int l
=1,int r
=n
)
{
if(ql
<=l
&&r
<=qr
) return (void)(sum
[k
]=(sum
[k
]+(r
-l
+1)*d
%mod
)%mod
,lzy
[k
]+=d
,lzy
[k
]%=mod
);
pushdown(k
,l
,r
);int mid
=l
+r
>>1;
if(ql
<=mid
) Modify_add(ql
,qr
,d
,lson
,l
,mid
);
if(qr
>mid
) Modify_add(ql
,qr
,d
,rson
,mid
+1,r
);
return (void)(sum
[k
]=(sum
[lson
]+sum
[rson
])%mod
);
}
inline void Modify_mul(int ql
,int qr
,LL d
,int k
=1,int l
=1,int r
=n
)
{
if(ql
<=l
&&r
<=qr
) return (void)(sum
[k
]=sum
[k
]*d
%mod
,mul
[k
]=mul
[k
]*d
%mod
,lzy
[k
]=lzy
[k
]*d
%mod
);
pushdown(k
,l
,r
);int mid
=l
+r
>>1;
if(ql
<=mid
) Modify_mul(ql
,qr
,d
,lson
,l
,mid
);
if(qr
>mid
) Modify_mul(ql
,qr
,d
,rson
,mid
+1,r
);
return (void)(sum
[k
]=(sum
[lson
]+sum
[rson
])%mod
);
}
inline LL
Query(int ql
,int qr
,int k
=1,int l
=1,int r
=n
)
{
if(ql
<=l
&&r
<=qr
) return sum
[k
];
LL res
=0;int mid
=l
+r
>>1;
pushdown(k
,l
,r
);
if(ql
<=mid
) res
=(res
+Query(ql
,qr
,lson
,l
,mid
))%mod
;
if(qr
>mid
) res
=(res
+Query(ql
,qr
,rson
,mid
+1,r
))%mod
;
return res
;
}
}T
;
inline LL
read()
{
char c
;LL d
=1,f
=0;
while(c
=getchar(),!isdigit(c
)) if(c
=='-') d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
signed main()
{
n
=read();m
=read();mod
=read();
for(register int i
=1;i
<=n
;i
++) a
[i
]=read();
T
.build();
while(m
--)
{
opt
=read();
if(opt
==1)
{
l
=read();r
=read();x
=read()%mod
;
T
.Modify_mul(l
,r
,x
);
}
if(opt
==2)
{
l
=read();r
=read();x
=read()%mod
;
T
.Modify_add(l
,r
,x
);
}
if(opt
==3)
{
l
=read();r
=read();
printf("%lld\n",T
.Query(l
,r
));
}
}
}
