1.乘法线段树
顾名思义，就是其中的区间修改为乘法，但是呢，如果只是一个乘法，把之前的加号变成*号，然后开long long即可（因为乘法的数据超大，如果不在中间mod点儿东西还能直接超出64位）
当lz下标传递的时候，我们需要考虑乘法和加法的运算的先后顺序。我们只需要对l做这样一个处理。
lazytage分为两种，分别是加法的add和乘法的mul。
mul很简单处理，pushdown时直接*父亲的就可以了，那么加法呢？
我们需要把原先的add*父亲的mul再加上父亲的add.
所以我们pushdown函数会有所改变
void pushdown(long long i)
{
long long k1=tree[i].mul,k2=tree[i].add;
tree[i*2].sum=(long long)(tree[i*2].sum*k1+(k2*(tree[i*2].r-tree[i*2].l+1))%m)%m;
tree[i*2].mul=(long long)(tree[i*2].mul*k1)%m;
tree[i*2].add=(long long)(tree[i*2].add*k1+k2)%m;
tree[i*2+1].sum=(long long)(tree[i*2+1].sum*k1+(k2*(tree[i*2+1].r-tree[i*2+1].l+1)%m))%m;
tree[i*2+1].mul=(long long)(tree[i*2+1].mul*k1)%m;
tree[i*2+1].add=(long long)(tree[i*2+1].add*k1+k2)%m;
tree[i].add=0;
tree[i].mul=1;
return ;
}2.例题
1.模版线段树2
题解：标准的乘法线段树
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
long long n,q,m;
long long a[100005];
long long flag;
long long ans;
struct node{
long long l;
long long r;
long long sum;
long long mul;
long long add;
}tree[100005*4];
void build(long long i,long long l,long long r)
{
tree[i].l=l;
tree[i].r=r;
tree[i].mul=1;
if(l==r)
{
tree[i].sum=a[l]%m;
return ;
}
int mid=l+r>>1;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%m;
}
void pushdown(long long i)
{
long long k1=tree[i].mul,k2=tree[i].add;
tree[i*2].sum=(long long)(tree[i*2].sum*k1+(k2*(tree[i*2].r-tree[i*2].l+1))%m)%m;
tree[i*2].mul=(long long)(tree[i*2].mul*k1)%m;
tree[i*2].add=(long long)(tree[i*2].add*k1+k2)%m;
tree[i*2+1].sum=(long long)(tree[i*2+1].sum*k1+(k2*(tree[i*2+1].r-tree[i*2+1].l+1)%m))%m;
tree[i*2+1].mul=(long long)(tree[i*2+1].mul*k1)%m;
tree[i*2+1].add=(long long)(tree[i*2+1].add*k1+k2)%m;
tree[i].add=0;
tree[i].mul=1;
return ;
}
void add(long long i,long long l,long long r,long long k)
{
if(tree[i].r<=r&&tree[i].l>=l)//如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
{
tree[i].add=(long long)(tree[i].add+k)%m;
tree[i].sum=(long long)(tree[i].sum+k*(tree[i].r-tree[i].l+1))%m;
return ;
}
pushdown(i);//向下传递
if(tree[i*2].r>=l)
add(i*2,l,r,k);
if(tree[i*2+1].l<=r)
add(i*2+1,l,r,k);
tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%m;
return ;
}
void mul(long long i,long long l,long long r,long long k)
{
if(tree[i].r<=r&&tree[i].l>=l)//如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
{
tree[i].mul=(long long)(tree[i].mul*k)%m;
tree[i].add=(long long)(tree[i].add*k)%m;
tree[i].sum=(long long)(tree[i].sum*k)%m;
return ;
}
pushdown(i);//向下传递
if(tree[i*2].r>=l)
mul(i*2,l,r,k);
if(tree[i*2+1].l<=r)
mul(i*2+1,l,r,k);
tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%m;
return ;
}
long long cha(long long i,long long l,long long r)
{
if(tree[i].l>=l && tree[i].r<=r)
return tree[i].sum;
if(tree[i].r<l || tree[i].l>r)
return 0;
pushdown(i);
long long s=0;
if(tree[i*2].r>=l)
s=(s+cha(i*2,l,r))%m;
if(tree[i*2+1].l<=r)
s=(s+cha(i*2+1,l,r))%m;
return s;
}
int main()
{
cin>>n>>q>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
while(q--)
{
cin>>flag;
if(flag==1)
{
int x,y,z;
cin>>x>>y>>z;
mul(1,x,y,z);
}
else if(flag==2)
{
int x,y,z;
cin>>x>>y>>z;
add(1,x,y,z);
}
else
{
ans=0;
int x,y;
cin>>x>>y;
ans=cha(1,x,y)%m;
printf("%lld\n",ans);
}
}
return 0;
}
