洛谷P2023：https://www.luogu.org/problemnew/show/P2023
思路
需要2个Lazy-Tag
一个表示加的 一个表示乘的
需要先计算乘法 再计算加法
来自你谷milkfilling大佬的解释：
①加法优先，即规定好segtree[root*2].value=((segtree[root*2].value+segtree[root].add)*segtree[root].mul)%p，问题是这样的话非常不容易进行更新操作，假如改变一下add的数值，mul也要联动变成奇奇怪怪的分数小数损失精度，我们内心是很拒绝的；
②乘法优先，即规定好segtree[root*2].value=(segtree[root*2].value*segtree[root].mul+segtree[root].add*(本区间长度))%p，这样的话假如改变add的数值就只改变add，改变mul的时候把add也对应的乘一下就可以了，没有精度损失，看起来很不错。
所以这道题就是模板题啦~
易错点会在代码中详细注释出来
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 100007
#define ll long long
ll sum[maxn<<
2],add[maxn<<
2],mul[maxn<<
2],a[maxn],n,m,p;
void build(ll l,ll r,ll k)
{
mul[k]=
1;
//初始化标记
if(l==
r)
{
sum[k]=a[l]%
p;
mul[k]=
1;
return;
}
ll mid=(l+r)>>
1;
build(l,mid,k<<
1);
//左右子树构建
build(mid+
1,r,k<<
1|
1);
sum[k]=(sum[k<<
1]+sum[k<<
1|
1])%p;
//维护sum值
}
void pushdown(ll l,ll r,ll mid,ll k)
//标记下放
{
//先乘后加
if(mul[k]!=
1)
//当有乘法标记 计算所有的值
{
sum[k<<
1]=(sum[k<<
1]*mul[k])%
p;
sum[k<<
1|
1]=(sum[k<<
1|
1]*mul[k])%
p;
mul[k<<
1]=(mul[k<<
1]*mul[k])%
p;
mul[k<<
1|
1]=(mul[k<<
1|
1]*mul[k])%
p;
add[k<<
1]=(add[k<<
1]*mul[k])%p;
//加法标记也要乘
add[k<<
1|
1]=(add[k<<
1|
1]*mul[k])%
p;
mul[k]=
1;
//清除标记
}
if(add[k])
//当有加法标记
{
sum[k<<
1]=(sum[k<<
1]+add[k]*(mid-l+
1)%p)%p;
//左右子树计算 右子树不用+1
sum[k<<
1|
1]=(sum[k<<
1|
1]+add[k]*(r-mid)%p)%p;
//注意这里要先算sum 再算add
add[k<<
1]=(add[k]+add[k<<
1])%p;
//如果先算add 那再sum中的add值已经改变
add[k<<
1|
1]=(add[k]+add[k<<
1|
1])%p;
//坑了我一个晚上（太弱了）
add[k]=
0;
//清除标记
}
return;
}
void update1(ll x,ll y,ll v,ll l,ll r,ll k)
//在定区间[x,y]加上v
{
if(l>=x&&r<=y)
//如果整个区间包含
{
add[k]=(add[k]+v)%
p;
sum[k]=(sum[k]+(r-l+
1)*v)%
p;
return;
}
ll mid=(l+r)>>
1;
pushdown(l,r,mid,k);
if(x<=mid) update1(x,y,v,l,mid,k<<
1);
if(mid<y) update1(x,y,v,mid+
1,r,k<<
1|
1);
sum[k]=(sum[k<<
1]+sum[k<<
1|
1])%p;
//计算标记下放之后的值
return;
}
void update2(ll x,ll y,ll v,ll l,ll r,ll k)
//在定区间[x,y]乘上v
{
if(l>=x&&r<=y)
//如果整个区间包含
{
mul[k]=(mul[k]*v)%
p;
add[k]=(add[k]*v)%
p;
sum[k]=(sum[k]*v)%
p;
return;
}
ll mid=(l+r)>>
1;
pushdown(l,r,mid,k);
if(x<=mid) update2(x,y,v,l,mid,k<<
1);
if(mid<y) update2(x,y,v,mid+
1,r,k<<
1|
1);
sum[k]=(sum[k<<
1]+sum[k<<
1|
1])%p;
//计算标记下放之后的值
return;
}
ll query(ll x,ll y,ll l,ll r,ll k)
{
if(l>=x&&r<=y)
return sum[k]%
p;
ll mid=(l+r)>>
1;
ll res=
0;
pushdown(l,r,mid,k);//标记下放
if(x<=mid) res+=query(x,y,l,mid,k<<
1);
res%=
p;
if(y>mid) res+=query(x,y,mid+
1,r,k<<
1|
1);
return res%
p;
}
int main()
{
cin>>n>>
p;
for(ll i=
1;i<=n;i++) cin>>
a[i];
cin>>
m;
build(1,n,
1);
for(ll i=
1;i<=m;i++
)
{
ll x,y,z;
cin>>
x;
if(x==
1)
{
cin>>x>>y>>
z;
update2(x,y,z,1,n,
1);
}
else if(x==
2)
{
cin>>x>>y>>
z;
update1(x,y,z,1,n,
1);
}
else if(x==
3)
{
cin>>x>>
y;
cout<<query(x,y,
1,n,
1)<<
endl;
}
}
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9757312.html
相关资源：JAVA上百实例源码以及开源项目
