P3373 【模板】线段树2 题解

本文主要是介绍P3373 【模板】线段树2 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目链接】P3373 【模板】线段树 2

【思路】

本题复杂在于有两个优先级不同的区间修改操作。考虑遵循乘法优先，那么维护两个懒标记mul（乘）和add（加），打加法标记按照普通方法，打乘法标记要注意把加法标记也乘一下要乘的数。加法标记的下传，要先把原标记乘上乘法标记（乘法优先）

举个例子：

假设一个长度为5的区间的和为25，现要把区间每个数加上5再乘上5，那么打乘法标记时，加法标记就应变为5*5=25，那么维护该区间的值时，这个区间的值就应该是25*5+5*5*5=250，类似于乘法分配律的思想。先乘后加也是一样的推导：打乘法标记时，加法标记变为0*5=0，后来加法打上标记5，维护区间值时，这个区间的值就应该是25*5+5*5=150。

【Code】

#include<iostream>
#include<cstdio>
using namespace std;
struct Segment_Tree{long long sum;long long mul,add;
}tree[500000];
long long a[100100],kk;
int p,n,m,op,ll,rr;
inline void build(int k,int l,int r){tree[k].add=0;tree[k].mul=1;if(l==r){tree[k].sum=a[l]%p;return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tree[k].sum=(tree[k<<1].sum+tree[k<<1|1].sum)%p;
}
inline void pushdown(int k,int l,int r){int mid=(l+r)>>1;tree[k<<1].sum=(tree[k<<1].sum*tree[k].mul+tree[k].add*(mid-l+1))%p;tree[k<<1|1].sum=(tree[k<<1|1].sum*tree[k].mul+tree[k].add*(r-mid))%p;if(tree[k].add){tree[k<<1].add=(tree[k<<1].add*tree[k].mul+tree[k].add)%p;tree[k<<1|1].add=(tree[k<<1|1].add*tree[k].mul+tree[k].add)%p;tree[k].add=0;}if(tree[k].mul!=1){tree[k<<1].mul=(tree[k<<1].mul*tree[k].mul)%p;tree[k<<1|1].mul=(tree[k<<1|1].mul*tree[k].mul)%p;tree[k].mul=1;}
}
inline long long Ask(int k,int l,int r,int x,int y){if(x>r||l>y)return 0;if(x<=l&&y>=r)return tree[k].sum;pushdown(k,l,r);int mid=(l+r)>>1;long long res=0;if(x<=mid)res+=Ask(k<<1,l,mid,x,y);if(y>mid)res+=Ask(k<<1|1,mid+1,r,x,y);return res%p;
}
inline void modify_add(int k,int l,int r,int x,int y,long long v){if(y<l||r<x)return;if(x<=l&&r<=y){tree[k].add=(tree[k].add+v)%p;tree[k].sum=(tree[k].sum+v*(r-l+1))%p;return;}pushdown(k,l,r);int mid=(l+r)>>1;if(x<=mid)modify_add(k<<1,l,mid,x,y,v);if(y>mid)modify_add(k<<1|1,mid+1,r,x,y,v);tree[k].sum=(tree[k<<1].sum+tree[k<<1|1].sum)%p;
}
inline void modify_mul(int k,int l,int r,int x,int y,long long v){if(y<l||r<x)return;if(x<=l&&r<=y){tree[k].mul=(tree[k].mul*v)%p;tree[k].sum=(tree[k].sum*v)%p;tree[k].add=(tree[k].add*v)%p;return;}pushdown(k,l,r);int mid=(l+r)>>1;if(x<=mid)modify_mul(k<<1,l,mid,x,y,v);if(y>mid)modify_mul(k<<1|1,mid+1,r,x,y,v);tree[k].sum=(tree[k<<1].sum+tree[k<<1|1].sum)%p;
}
int main(){scanf("%d%d%d",&n,&m,&p);for(register int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,1,n);for(register int i=1;i<=m;i++){scanf("%d",&op);if(op==1){scanf("%d%d%lld",&ll,&rr,&kk);modify_mul(1,1,n,ll,rr,kk);}else{if(op==2){scanf("%d%d%lld",&ll,&rr,&kk);modify_add(1,1,n,ll,rr,kk);}else{scanf("%d%d",&ll,&rr);printf("%lld\n",Ask(1,1,n,ll,rr));}}}return 0;
}

这篇关于P3373 【模板】线段树2 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---