题目描述

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

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的结果。

---

这题需要用线段树进行两种运算，所以我们需要记录两个延迟标记，但如何用延迟标记进行更新就成了最主要的问题：

我们将区间和写成这种形式：

\[ len=t[d].r-t[d].l+1\\ t[d].val=(t[d].val+t[d].add*len)*t[d].mul \]

然后我们对加法标记加一个值时就会变成：

\[ t[d].val+val=(t[d].val+t[d].add*len)*t[d].mul+val*len \]

于是我们发现，如果要把这个式子写成最初的形式，就不免把val * len改成x * t[d].mul的形式，然而x很容易就变成小数了。考虑到精度，我们选择放弃这种方法。

换一种形式：

\[ t[d].val=t[d].val*t[d].mul+t[d].add*len \]

乘上一个值时就会变成：

\[ t[d].val*val=(t[d].val*t[d].mul+t[d].add*len)*val\\ =t[d].val*t[d].mul*val+t[d].add*val*len \]

也就是说，我们只需要给加法标记和乘法标记都乘上这个值即可。加上一个值时：

\[ t[d].val+val=t[d].val*t[d].mul+t[d].add*len+val*len\\ =t[d].val*t[d].mul+(t[d].add+val)*len \]

我们只需要把加法标记加上这个值即可。我们便可以很方便得解决这道题了。

时间复杂度为O(NlogN)。

#include
    
     #include
     
      #include
      
       #define maxn 100001using namespace std;int n,m,mod,val[maxn];inline int read(){    register int x(0),f(1); register char c(getchar());    while(c<'0'||'9'
       
        >1;    build(d<<1,l,mid),build(d<<1|1,mid+1,r);    t[d].val=(t[d<<1].val+t[d<<1|1].val) % mod;}void change_mul(int d,const int &l,const int &r,const int &val){    if(l<=t[d].l&&t[d].r<=r){        t[d].val=(t[d].val*val) % mod,t[d].mul=(t[d].mul*val) % mod,t[d].add=(t[d].add*val) % mod;        return;    }    down(d);    int mid=t[d].l+t[d].r>>1;    if(l<=mid) change_mul(d<<1,l,r,val);    if(r>mid) change_mul(d<<1|1,l,r,val);    t[d].val=(t[d<<1].val+t[d<<1|1].val) % mod;}void change_add(int d,const int &l,const int &r,const int &val){    if(l<=t[d].l&&t[d].r<=r){        t[d].val=(t[d].val+(t[d].r-t[d].l+1)*val % mod) % mod,t[d].add=(t[d].add+val) % mod;        return;    }    down(d);    int mid=t[d].l+t[d].r>>1;    if(l<=mid) change_add(d<<1,l,r,val);    if(r>mid) change_add(d<<1|1,l,r,val);    t[d].val=(t[d<<1].val+t[d<<1|1].val) % mod;}long long getsum(int d,const int &l,const int &r){    if(l<=t[d].l&&t[d].r<=r) return t[d].val;    down(d);    int mid=t[d].l+t[d].r>>1;    long long ans=0ll;    if(l<=mid) ans=(ans+getsum(d<<1,l,r)) % mod;    if(r>mid) ans=(ans+getsum(d<<1|1,l,r)) % mod;    return ans;}int main(){    n=read(),m=read(),mod=read();    for(register int i=1;i<=n;i++) val[i]=read();    build(1,1,n);    for(register int i=1;i<=m;i++){        int op=read(),l=read(),r=read();        if(op==1) change_mul(1,l,r,read());        if(op==2) change_add(1,l,r,read());        if(op==3) printf("%lld\n",getsum(1,l,r));    }    return 0;}