专栏文章

题解：P3373 【模板】线段树 2

xxiaolongmei
P3373题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipsfree
此快照首次捕获于
2025/12/03 17:11
3 个月前
此快照最后确认于
2025/12/03 17:11
3 个月前
查看原文
链接
温馨提示：因为作者非常懒，所以与线段树 1 相同的地方会没有任何注释！！！

思路

有了线段树 1 的基础，我们可以直接考虑在线段树 1 的代码中修改，使这个代码能实现 +、×+、× 两种操作 这样想的话，我们就应该需要两种懒标记 (一个+，一个×)(一个+，一个×)

定义

CPP
struct inf{ll l,r,sum,la,lm;}t[4*N];/*la=lazy add lm=lazy multiplication(乘法)*/

主函数

变化很少
CPP
int main(){
	cin>>n>>q>>mod;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(q--){
		cin>>op>>x>>y;
		if(op==1)cin>>k,update(1,k,0);/*多了一个乘法要乘的数，和加法要加的数*/
		else if(op==2)cin>>k,update(1,1,k);/*同上*/
		else cout<<query(1)<<"\n";
	}
	return 0;
}

建树 (build)

几乎没有什么变化
CPP
void build(ll p,ll l,ll r){
	t[p]={l,r,a[l],0,1};/*乘法标记依次累乘所以用1*/
	if(l==r)return;
	ll mid=l+r>>1;
	build(2*p,l,mid),build(2*p+1,mid+1,r);
	pushup(p);
}
pushuppushup 只需在原基础上 % 输入的模数即可

更新区间值

接下来我们只需要在 pushdownpushdown 中加入乘法就好啦！ 可是，应该先乘还是先加呢？如果我们先加后乘 ( xx 是要加的值) 假设，父节点的懒标记为 m(×)m(×) 和 a(+)a(+) , 子节点懒标记为 lm(×)lm(×) 和 la(+)la(+) 则区间值：(((x+la)×lm)+a)×m(((x+la)×lm)+a)×m =(x×lm+la×lm+a)×m=(x×lm+la×lm+a)×m =x×lm×m+la×lm×m+a×m=x×lm×m+la×lm×m+a×m =(x+la+a÷lm)×lm×m=(x+la+a÷lm)×lm×m 这样就有了精度上的问题了，所以我们就先乘后加假设，父节点的懒标记为 m(×)m(×) 和 a(+)a(+) , 子节点懒标记为 lm(×)lm(×) 和 la(+)la(+) 则区间值：(x×lm+la)×m+a(x×lm+la)×m+a =x×(lm×m)+(la×m+a)=x×(lm×m)+(la×m+a) 子节点的 lm=lm×mlm=lm×m , la=la×m+ala=la×m+a

计算子节点的 sumsum

设父节点的懒标记为 mm 和 aa，子节点 sumsum , 则子节点 sum 为：(xl×m+a)+...+(xr×m+a)(x_l×m+a)+...+(x_r×m+a) =(xl+...+xr)×m+(r−l+1)×a=(x_l+...+x_r)×m+(r-l+1)×a =sum×m+(r−l+1)×a=sum×m+(r-l+1)×a
注意：下传后，清空懒标记：m=1,a=0m=1,a=0

代码

CPP
void pushdown(ll p){
	js(2*p,t[p].lm,t[p].la),js(2*p+1,t[p].lm,t[p].la);/*更新左右节点*/
	t[p].la=0,t[p].lm=1;/*乘法不写1就废了*/
}
下面提供更新部分
CPP
void js(ll p,ll m,ll a){/*要更新的节点编号和它的父节点的两个标记*/
	t[p].sum=(t[p].sum*m+(t[p].r-t[p].l+1)*a)%mod;/*要乘的+要加的*/
	t[p].lm=t[p].lm*m%mod;/*更新乘法标记*/
	t[p].la=(t[p].la*m+a)%mod;/*更新加法标记*/
}

区间修改

改动不多，直接上代码！！！
CPP
void update(ll p,ll m,ll a){
	if(t[p].l>y||t[p].r<x)return;/*完全没有交集直接退出*/
	if(t[p].l>=x&&t[p].r<=y){js(p,m,a);return;}/*完全覆盖更新这个节点的值*/
	pushdown(p);
	update(2*p,m,a),update(2*p+1,m,a);
	pushup(p);
}

区间查询

改动不多，直接上代码！！！
CPP
ll query(ll p){
	if(y<t[p].l||x>t[p].r)return 0;/*完全不覆盖退出*/
	if(t[p].l>=x&&t[p].r<=y)return t[p].sum;/*完全覆盖，返回*/
	pushdown(p);
	return (query(2*p)+query(2*p+1))%mod;/*两者和%mod*/
}
还是挺好理解的，送个完整代码吧！

完整代码

懒得再打一边注释了，不懂的上面看看吧！
CPP
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define N 100005
using namespace std;
struct inf{ll l,r,sum,la,lm;}t[4*N];/*la=lazy add lm=lazy mul....*/
ll n,q,mod,a[N],op,x,y,k;
void pushup(ll p){t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;}
void js(ll p,ll m,ll a){
	t[p].sum=(t[p].sum*m+(t[p].r-t[p].l+1)*a)%mod;
	t[p].lm=t[p].lm*m%mod;
	t[p].la=(t[p].la*m+a)%mod;
}
void pushdown(ll p){
	js(2*p,t[p].lm,t[p].la),js(2*p+1,t[p].lm,t[p].la);
	t[p].la=0,t[p].lm=1;
}
void build(ll p,ll l,ll r){
	t[p]={l,r,a[l],0,1};
	if(l==r)return;
	ll mid=l+r>>1;
	build(2*p,l,mid),build(2*p+1,mid+1,r);
	pushup(p);
}
void update(ll p,ll m,ll a){
	if(t[p].l>y||t[p].r<x)return;
	if(t[p].l>=x&&t[p].r<=y){js(p,m,a);return;}
	pushdown(p);
	update(2*p,m,a),update(2*p+1,m,a);
	pushup(p);
}
ll query(ll p){
	if(y<t[p].l||x>t[p].r)return 0;
	if(t[p].l>=x&&t[p].r<=y)return t[p].sum;
	pushdown(p);
	return (query(2*p)+query(2*p+1))%mod;
}
int main(){
	cin>>n>>q>>mod;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(q--){
		cin>>op>>x>>y;
		if(op==1)cin>>k,update(1,k,0);
		else if(op==2)cin>>k,update(1,1,k);
		else cout<<query(1)<<"\n";
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...