bzoj 1798 维护序列seq

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1798

题解：

　　高级一点的线段树，加上了区间乘法运算，则需要增加一个数组mulv记录乘的因数，在下放更新sumv和addv值的都时候要先乘再加

　　被蓝书的写法坑了，就一直搞不懂下放和sumv、addv数组的具体用法，导致网上大犇们的程序我基本都看不懂，写完这道题感觉重新学了一遍线段树

 #include<cstdio>

 #include<cstring>

 #define MAXN 400010

 #define LL long long

 LL MOD,sumv[MAXN],addv[MAXN],mulv[MAXN];

 int n,m,t1,y1,y2,v;

 void maintain(int o,int len)//下放

 {

     int lc=o<<,rc=(o<<)+,M=len>>;

     if(mulv[o]!=||addv[o])

     {

         mulv[lc]=(mulv[lc]*mulv[o])%MOD;

         mulv[rc]=(mulv[rc]*mulv[o])%MOD;

         addv[lc]=((addv[lc]*mulv[o])+addv[o])%MOD;

         addv[rc]=((addv[rc]*mulv[o])+addv[o])%MOD;

         sumv[lc]=(sumv[lc]*mulv[o]+(len-M)*addv[o])%MOD;

         sumv[rc]=(sumv[rc]*mulv[o]+M*addv[o])%MOD;

     }

     addv[o]=;

     mulv[o]=;

 }

 void build(int o,int L,int R)

 {

     int lc=o<<,rc=(o<<)+,M=(L+R)/;

     if(L==R)

     {

         scanf("%lld",&sumv[o]);

         return;

     }

     build(lc,L,M);

     build(rc,M+,R);

     sumv[o]=(sumv[lc]+sumv[rc])%MOD;

 }

 void update(int o,int L,int R)

 {

     int lc=o<<,rc=(o<<)+,M=(L+R)/;

     if(y1<=L&&y2>=R)

     {

         if(t1==)

         {

             addv[o]=(addv[o]*v)%MOD;

             sumv[o]=(sumv[o]*v)%MOD;

             mulv[o]=(mulv[o]*v)%MOD;

         }

         else

         {

             addv[o]=(addv[o]+v)%MOD;

             sumv[o]=(sumv[o]+v*(R-L+))%MOD;

         }

         return;

     }

     maintain(o,R-L+);

     if(y1<=M)update(lc,L,M);

     if(y2>M)update(rc,M+,R);

     sumv[o]=(sumv[lc]+sumv[rc])%MOD;

 }

 LL query(int o,int L,int R)

 {

     int lc=o<<,rc=(o<<)+,M=(L+R)>>;

     if(y1<=L&&y2>=R)return sumv[o]%MOD;

     maintain(o,R-L+);

     LL ans=;

     if(y1<=M)ans=(query(lc,L,M))%MOD;

     if(y2>M)ans+=(query(rc,M+,R))%MOD;

     sumv[o]=(sumv[lc]+sumv[rc])%MOD;

     return ans%MOD;

 }

 int main()

 {

     scanf("%d%lld",&n,&MOD);

     for(int i=;i<=;i++)mulv[i]=;

     build(,,n);

     scanf("%d",&m);

     while(m--)

     {

         scanf("%d%d%d",&t1,&y1,&y2);

         if(t1!=)

         {

             scanf("%d",&v);

             update(,,n);

         }

         else printf("%lld\n",query(,,n));

     }

     return ;

 }