题目描述

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

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

（数据已经过加强^_^）

样例说明：

故输出应为17、2（40 mod 38=2）

思路

这个题数据特别大，在有区间加法的同时，还增加了区间乘法,这就是难度增大了

引用:milkfilling的题解

面对这两种操作，可以联想到线段树的一个非常好的功能就是lazytag，只计算出确实需要访问的区间的真实值，其他的保存在lazytag里面，这样可以近似O(NlogN)的运行起来。在尝试着写了只有一个lazetag的程序之后我们发现一个lazytag是不能够解决问题的，那就上两个，分别表示乘法意义上的lazytag和加法意义上的lazytag。紧接着想到pushdown操作之后我们又发现必须在向下传递lazytag的时候人为地为这两个lazytag规定一个先后顺序，排列组合一下只有两种情况：

①加法优先，即规定好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也对应的乘一下就可以了，没有精度损失，看起来很不错。

所以我们在线段树pushdown向下更新的时候,先更新区间和的左右儿子，根据我们规定的优先度，儿子的值=此刻儿子的值*爸爸的乘法lazy+儿子的区间长度*爸爸的加法lazy，然后再分别维护乘法的lazy和加法的lazy，最后取消标记

在update更新的时候，当更新到乘法的时候，需要更新区间和，乘法lazy和加法lazy;当更新加法的时候，只需要更新区间和和加法的lazy就可以了。

还有不要忘记对p取模,数据很大需要用到long long

代码

#include <bits/stdc++.h> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define mem(a,b) mem(a,b,sizeof(a)) typedef long long ll; const ll N=100000+20; ll mul[N<<2],add[N<<2];//两个lazy标记 ll sum[N<<2],p; void pushup(ll rt) { sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%p; } void build(ll l,ll r,ll rt) { mul[rt]=1; add[rt]=0; if(l==r) { scanf("%lld",&sum[rt]); sum[rt]%=p; return; } ll m=(l+r)>>1; build(lson); build(rson); pushup(rt); } void pushdown(ll l,ll r,ll rt) { ll m=(l+r)>>1; sum[rt<<1]=(sum[rt<<1]*mul[rt]+add[rt]*(m-l+1))%p; sum[rt<<1|1]=(sum[rt<<1|1]*mul[rt]+add[rt]*(r-m))%p; //维护lazy mul[rt<<1]=(mul[rt<<1]*mul[rt])%p; mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%p; add[rt<<1]=(add[rt<<1]*mul[rt]+add[rt])%p; add[rt<<1|1]=(add[rt<<1|1]*mul[rt]+add[rt])%p; //初始化父节点的lazy mul[rt]=1; add[rt]=0; } void update1(ll L,ll R,ll k,ll l,ll r,ll rt)//乘法 { if(L<=l&&r<=R) { sum[rt]=(sum[rt]*k)%p; mul[rt]=(mul[rt]*k)%p; add[rt]=(add[rt]*k)%p; return; } pushdown(l,r,rt); ll m=(l+r)>>1; if(L<=m) update1(L,R,k,lson); if(R>m) update1(L,R,k,rson); pushup(rt); return; } void update2(ll L,ll R,ll k,ll l,ll r,ll rt)//加法 { if(L<=l&&r<=R) { add[rt]=(add[rt]+k)%p; sum[rt]=(sum[rt]+k*(r-l+1))%p; return; } ll m=(l+r)>>1; pushdown(l,r,rt); if(L<=m) update2(L,R,k,lson); if(R>m) update2(L,R,k,rson); pushup(rt); return; } ll query(ll L,ll R,ll l,ll r,ll rt) { if(L<=l&&r<=R) return sum[rt]; ll m=(l+r)>>1; pushdown(l,r,rt); ll ans=0; if(L<=m) ans=(ans+query(L,R,lson))%p; if(R>m) ans=(ans+query(L,R,rson))%p; return ans; } int main() { ll n,m; scanf("%lld%lld%lld",&n,&m,&p); build(1,n,1); ll x,y,k,op; for(ll i=1; i<=m; i++) { scanf("%lld",&op); if(op==1) { scanf("%lld%lld%lld",&x,&y,&k); update1(x,y,k,1,n,1); } else if(op==2) { scanf("%lld%lld%lld",&x,&y,&k); update2(x,y,k,1,n,1); } else { scanf("%lld%lld",&x,&y); printf("%lld\n",query(x,y,1,n,1)); } } return 0; }