本文主要是介绍HYSBZ - 1798 Seq 维护序列seq 线段树lazy标记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
这道题属实是线段树的道比刷题，又加又乘的，当然还可能会有乘除，阶乘等等可能的情况。
对于这道题，主要的一个就是怎么记录lazy标记，首先的话一个数组是肯定不行的，设乘的为lazy，加的为add。
每次我们更新时，要用lazy数组去更新add数组。
关键是pushdown的时候注意一下，下放的时候比较复杂。
代码如下：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
using namespace std;
const int maxn=1e5+5;
ll mod,n,m;
ll tree[maxn<<2],lazy[maxn<<2],add[maxn<<2],a[maxn];
void pushup(int i,int l,int r)
{tree[i]=(tree[lson]+tree[rson])%mod;
}
///i表示父亲，lson左儿子，rson右儿子，lazy记录乘，add记录加
void pushdown(int i,int l,int r)
{if(lazy[i]==1&&add[i]==0)//如果乘的为1,加的为0,就不做处理return;int mid=half;lazy[lson]=lazy[i]*lazy[lson]%mod;add[lson]=(lazy[i]*add[lson]%mod+add[i])%mod;tree[lson]=(lazy[i]*tree[lson]%mod+add[i]*(mid-l+1)%mod)%mod;lazy[rson]=lazy[rson]*lazy[i]%mod;add[rson]=(lazy[i]*add[rson]%mod+add[i])%mod;tree[rson]=(lazy[i]*tree[rson]%mod+add[i]*(r-mid)%mod)%mod;lazy[i]=1;add[i]=0;
}
void update(int i,int l,int r,ll ql,ll qr,ll val,ll x)
{if(ql<=l&&qr>=r){if(x==1){lazy[i]=lazy[i]*val%mod;add[i]=add[i]*val%mod;tree[i]=tree[i]*val%mod;}else{add[i]=(add[i]+val)%mod;tree[i]=(tree[i]+(r-l+1)*val)%mod;}return;}pushdown(myself);int mid=half;if(qr<=mid) update(Lson,ql,qr,val,x);else if(ql>mid) update(Rson,ql,qr,val,x);else{update(Lson,ql,mid,val,x);update(Rson,mid+1,qr,val,x);}pushup(myself);
}
ll query(int i,int l,int r,ll ql,ll qr)
{if(ql<=l&&qr>=r)return tree[i]%mod;pushdown(myself);int mid=half;ll ans=0;if(ql<=mid) ans=(ans+query(Lson,ql,qr))%mod;if(qr>mid) ans=(ans+query(Rson,ql,qr))%mod;return ans;
}
void build(int i,int l,int r)
{lazy[i]=1;add[i]=0;if(l==r){tree[i]=a[l];return ;}int mid=half;build(Lson);build(Rson);pushup(myself);
}
int main()
{while(scanf("%lld %lld",&n,&mod)!=EOF){for(int i=1;i<=n;i++){scanf("%lld",&a[i]);a[i]%=mod;}build(1,1,n);scanf("%lld",&m);ll num,x,y,z;while(m--){scanf("%lld",&num);if(num!=3){scanf("%lld %lld %lld",&x,&y,&z);update(1,1,n,x,y,z,num);}else{scanf("%lld %lld",&x,&y);printf("%lld\n",query(1,1,n,x,y)%mod);}}}return 0;
}
这篇关于HYSBZ - 1798 Seq 维护序列seq 线段树lazy标记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
