【线段树2】洛谷P3373

时间:2022-12-17 20:05:40

题目描述

如题,已知一个数列,你需要进行下面三种操作:

1.将某区间每一个数乘上x

2.将某区间每一个数加上x

3.求出某区间每一个数的和

输入输出格式

输入格式:

 

第一行包含三个整数N、M、P,分别表示该数列数字的个数、操作的总个数和模数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数乘上k

操作2: 格式:2 x y k 含义:将区间[x,y]内每个数加上k

操作3: 格式:3 x y 含义:输出区间[x,y]内每个数的和对P取模所得的结果

 

输出格式:

 

输出包含若干行整数,即为所有操作3的结果。

 

输入输出样例

输入样例#1:
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
输出样例#1:
17
2

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=8,M<=10

对于70%的数据:N<=1000,M<=10000

对于100%的数据:N<=100000,M<=100000

(数据已经过加强^_^)

样例说明:

【线段树2】洛谷P3373

故输出应为17、2(40 mod 38=2)

/*****************************************************/

再来一篇线段树~

线段树1在这里哦~

//区间加法区间乘法
#include<iostream> #include<cstdio> #include<algorithm> #define ls step<<1 #define rs step<<1|1 #define ll long long using namespace std; const ll maxn=100020; ll n,m,p,tag[maxn<<2],w[maxn<<2],Tag[maxn<<2]; void Plus(ll step) { w[step]=(w[ls]+w[rs])%p; } void build(ll step,ll l,ll r) { Tag[step]=1;tag[step]=0; if(l==r) { scanf("%lld",&w[step]); w[step]%=p; return ; } ll mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); Plus(step); } void push_down(ll step,ll l,ll r) { ll mid=(l+r)>>1; w[ls]=(w[ls]*Tag[step]+(mid-l+1)*tag[step])%p; w[rs]=(w[rs]*Tag[step]+(r-mid)*tag[step])%p; Tag[ls]=(Tag[ls]*Tag[step])%p; Tag[rs]=(Tag[rs]*Tag[step])%p; tag[ls]=(tag[ls]*Tag[step]+tag[step])%p; tag[rs]=(tag[rs]*Tag[step]+tag[step])%p; Tag[step]=1;tag[step]=0; } void Update(ll step,ll k,ll l,ll r,ll nl,ll nr) { if(nl<=l&&r<=nr) { w[step]=(w[step]*k)%p; Tag[step]=(Tag[step]*k)%p; tag[step]=(tag[step]*k)%p; return ; } push_down(step,l,r); ll mid=(l+r)>>1; if(mid>=nl) Update(ls,k,l,mid,nl,nr); if(mid<nr) Update(rs,k,mid+1,r,nl,nr); Plus(step); } void update(ll step,ll k,ll l,ll r,ll nl,ll nr) { if(nl<=l&&r<=nr) { w[step]=(w[step]+(r-l+1)*k)%p; tag[step]=(tag[step]+k)%p; return ; } push_down(step,l,r); ll mid=(l+r)>>1; if(mid>=nl) update(ls,k,l,mid,nl,nr); if(mid<nr) update(rs,k,mid+1,r,nl,nr); Plus(step); } ll query(ll step,ll l,ll r,ll nl,ll nr) { ll ans=0; if(nl<=l&&r<=nr) return w[step]; push_down(step,l,r); ll mid=(l+r)>>1; if(mid>=nl) ans+=query(ls,l,mid,nl,nr); if(mid<nr) ans+=query(rs,mid+1,r,nl,nr); return ans; } int main() { scanf("%lld%lld%lld",&n,&m,&p); build(1,1,n); for(ll i=1;i<=m;i++) { ll q,x,y,k; scanf("%lld%lld%lld",&q,&x,&y); if(q==1)//乘法 { scanf("%lld",&k); Update(1,k,1,n,x,y); } else if(q==2)//加法 { scanf("%lld",&k); update(1,k,1,n,x,y); } else if(q==3) printf("%lld\n",query(1,1,n,x,y)%p); } return 0; }