洛谷 P2023 [AHOI2009]维护序列 || 线段树加法和乘法运算

原理倒是非常简单。设原数为x，加法的lazytag为b，乘法的lazytag为a，操作数为c，那么原式为ax+b，乘上c后(ax+b)c=(ac)*x+b*c，加上c后(ax+b)+c=ax+(b+c)，因此加法时只需要更新加法的lazytag，乘法的时候就需要同时乘乘法和加法的lazytag。（乘法时的操作曾经搞错）

有些细节却很难受啊...比如很容易忘记加取模（一般都是程序打完了之后再补上，但是这个程序要补的地方太多，容易漏，要小心），把乘法的lazytag初始化为1出错，很容易少几句话...

 //以下代码中：加important标记的是曾经缺少的，注释掉的是曾经多的

 #include<cstdio>

 #include<cstring>

 #define lc (num<<1)

 #define rc (num<<1|1)

 #define mid ((l+r)>>1)

 typedef long long LL;

 LL a[];

 LL tree[],laz[],laz2[];

 LL L,R,x,n,m,md;

 void build(LL l,LL r,LL num)

 {

     laz2[num]=;//important

     if(l==r)

     {

         tree[num]=a[l]%md;

         return;

     }

     build(l,mid,lc);

     build(mid+,r,rc);

     tree[num]=(tree[lc]+tree[rc])%md;

 }

 void pushdown(LL l,LL r,LL num)

 {

     if(laz2[num]!=)

     {

         laz2[lc]=(laz2[lc]*laz2[num])%md;

         laz2[rc]=(laz2[rc]*laz2[num])%md;

         /*important*/

         laz[lc]=(laz[lc]*laz2[num])%md;

         laz[rc]=(laz[rc]*laz2[num])%md;

         tree[lc]=(tree[lc]*laz2[num])%md;

         tree[rc]=(tree[rc]*laz2[num])%md;

         /*-important*/

         /*

         tree[lc]=(tree[lc]+(mid-l+1)*laz2[num])%md;

         tree[rc]=(tree[rc]+(r-mid)*laz2[num])%md;

         */

         laz2[num]=;

     }

     if(laz[num])

     {

         laz[lc]=(laz[lc]+laz[num])%md;

         laz[rc]=(laz[rc]+laz[num])%md;

         tree[lc]=(tree[lc]+(mid-l+)*laz[num]%md)%md;

         tree[rc]=(tree[rc]+(r-mid)*laz[num]%md)%md;

         laz[num]=;

     }

 }

 void update(LL l,LL r,LL num)

 {

     if(L<=l&&r<=R)

     {

         tree[num]=(tree[num]+(r-l+)*x)%md;

         laz[num]=(laz[num]+x)%md;

         return;

     }

     pushdown(l,r,num);

     if(L<=mid)    update(l,mid,lc);

     if(mid<R)    update(mid+,r,rc);//if(mid+1<=R)//等价

     /*important*/tree[num]=(tree[lc]+tree[rc])%md;

 }

 void update2(LL l,LL r,LL num)

 {

     if(L<=l&&r<=R)

     {

         tree[num]=(tree[num]*x)%md;

         /*importaant*/laz[num]=(laz[num]*x)%md;/*important*/

         laz2[num]=(laz2[num]*x)%md;

         return;

     }

     pushdown(l,r,num);

     if(L<=mid)    update2(l,mid,lc);

     if(mid<R)    update2(mid+,r,rc);//if(mid+1<=R)//等价

     /*important*/tree[num]=(tree[lc]+tree[rc])%md;

 }

 LL query(LL l,LL r,LL num)

 {

     if(L<=l&&r<=R)    return tree[num];

     pushdown(l,r,num);

     LL ans=;

     if(L<=mid)    ans=(ans+query(l,mid,lc))%md;

     if(mid<R)    ans=(ans+query(mid+,r,rc))%md;

     return ans;

 }

 int main()

 {

     LL i,t;

     scanf("%lld%lld%lld",&n,&m,&md);

     for(i=;i<=n;i++)

         scanf("%lld",&a[i]);//不应该将laz2[]=1写在此处important

     build(,n,);

     for(i=;i<=m;i++)

     {

         scanf("%lld",&t);

         if(t==)

         {

             scanf("%lld%lld%lld",&L,&R,&x);

             update(,n,);

         }

         else if(t==)

         {

             scanf("%lld%lld",&L,&R);

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

         }

         else

         {

             scanf("%lld%lld%lld",&L,&R,&x);

             update2(,n,);

         }

     }

     return ;

 }

巴特西

洛谷 P2023 [AHOI2009]维护序列 || 线段树加法和乘法运算

最新文章

热门文章