题目描述

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

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 381 5 4 2 32 1 4 13 2 51 2 4 22 3 5 53 1 4

输出样例#1：

172

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=8，M<=10

对于70%的数据：N<=1000，M<=10000

对于100%的数据：N<=100000，M<=100000

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

样例说明：

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

（模板题敲bi半天，结果在局部变量挂了，QAQ）

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define maxn 100005 6 #define LL long long 7 #define ll l,mid,rt<<1 8 #define rr mid+1,r,rt<<1|1 9 using namespace std;10 LL n,m,Mod,a[maxn],add[maxn<<2],mul[maxn<<2],sum[maxn<<2];11 LL read(){12     LL x=0,f=1;char ch=getchar();13     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}14     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}15     return x*f;16 }17 void build(LL l,LL r,LL rt){18     mul[rt]=1;add[rt]=0;19     if(l==r){20         sum[rt]=a[l];21         return ;22     }23     LL mid=(l+r)>>1;24     build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);25     sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%Mod;26 }27 void pushdown(LL rt,LL k){28     sum[rt<<1]=(sum[rt<<1]*mul[rt]+add[rt]*(k-(k>>1)))%Mod;29     sum[rt<<1|1]=(sum[rt<<1|1]*mul[rt]+add[rt]*(k>>1))%Mod;30     mul[rt<<1]=(mul[rt<<1]*mul[rt])%Mod;31     mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%Mod;32     add[rt<<1]=(add[rt<<1]*mul[rt]+add[rt])%Mod;33     add[rt<<1|1]=(add[rt<<1|1]*mul[rt]+add[rt])%Mod;34     mul[rt]=1;add[rt]=0;35 }36 void Add(LL ql,LL qr,LL v,LL l,LL r,LL rt){37     if(ql<=l&&r<=qr){38         add[rt]=(add[rt]+v)%Mod;39         sum[rt]=(sum[rt]+v*(r-l+1))%Mod;40         return ;41     }42     pushdown(rt,r-l+1);43     LL mid=(l+r)>>1;44     if(ql<=mid) Add(ql,qr,v,ll);45     if(mid
         
          >1;57     if(ql<=mid) Mul(ql,qr,v,ll);58     if(mid
          
           >1;64 pushdown(rt,r-l+1);65 LL tmp=0;66 if(ql<=mid) tmp=(tmp+query(ql,qr,ll))%Mod;67 if(mid