前往：我自己搭建的博客
题目
洛谷P3373线段树2
题解
此题关键在于处理两种延迟标记的关系。假设一个数x受到了+a操作后，又受到了*b操作，则(x+a)*b=x*b+a*b,相当于对x先*b,再+a*b。假设一个数x受到了*a操作后，又受到了+b操作，则x*a+b。这样就可以确定+标记和*标记的相对简单的操作顺序，即先处理乘法，后处理加法。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,m;
ll MOD;
ll a[maxn];
struct Segment_tree{ll l,r,sum,tag_add,tag_mul;}t[maxn<<2];
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r,t[p].tag_mul=1; //注意初始化乘法标记
if(l==r) {t[p].sum=a[l]; return;}
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%MOD;
}
inline void spread(int p)
{
if(t[p].tag_mul!=1)
{
t[p<<1].sum=t[p<<1].sum*t[p].tag_mul%MOD;
t[p<<1|1].sum=t[p<<1|1].sum*t[p].tag_mul%MOD;
t[p<<1].tag_add=(t[p<<1].tag_add*t[p].tag_mul)%MOD;
t[p<<1|1].tag_add=(t[p<<1|1].tag_add*t[p].tag_mul)%MOD;
t[p<<1].tag_mul=t[p<<1].tag_mul*t[p].tag_mul%MOD;
t[p<<1|1].tag_mul=t[p<<1|1].tag_mul*t[p].tag_mul%MOD;
t[p].tag_mul=1;
}
if(t[p].tag_add!=0)
{
t[p<<1].sum=(t[p<<1].sum+t[p].tag_add*(t[p<<1].r-t[p<<1].l+1)%MOD)%MOD;
t[p<<1|1].sum=(t[p<<1|1].sum+t[p].tag_add*(t[p<<1|1].r-t[p<<1|1].l+1)%MOD)%MOD;
t[p<<1].tag_add=(t[p<<1].tag_add+t[p].tag_add)%MOD;
t[p<<1|1].tag_add=(t[p<<1|1].tag_add+t[p].tag_add)%MOD;
t[p].tag_add=0;
}
}
void add(int p,int l,int r,ll k)
{
if(l<=t[p].l&&r>=t[p].r)
{
t[p].sum=(t[p].sum+k*(t[p].r-t[p].l+1)%MOD)%MOD;
t[p].tag_add=(t[p].tag_add+k)%MOD; return;
}
spread(p); int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) add(p<<1,l,r,k);
if(r>mid) add(p<<1|1,l,r,k);
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%MOD;
}
void mul(int p,int l,int r,ll k)
{
if(l<=t[p].l&&r>=t[p].r)
{
t[p].sum=t[p].sum*k%MOD;
t[p].tag_add=t[p].tag_add*k%MOD;
t[p].tag_mul=t[p].tag_mul*k%MOD;
return;
}
spread(p); int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) mul(p<<1,l,r,k);
if(r>mid) mul(p<<1|1,l,r,k);
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%MOD;
}
ll ask(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r) return t[p].sum;
spread(p); int ans=0,mid=(t[p].l+t[p].r)>>1;
if(l<=mid) ans=(ans+ask(p<<1,l,r))%MOD;
if(r>mid) ans=(ans+ask(p<<1|1,l,r))%MOD;
return ans;
}
int main()
{
scanf("%d%d%lld",&n,&m,&MOD);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int t,x,y; ll k;
scanf("%d%d%d",&t,&x,&y);
if(t==1) {scanf("%lld",&k); mul(1,x,y,k);}
else if(t==2) {scanf("%lld",&k); add(1,x,y,k);}
else printf("%lld\n",ask(1,x,y));
}
return 0;
}
