首页 > > 程序设计 > C/C++ >

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

2018-06-17 21:44:22来源：未知阅读 ()

原理倒是非常简单。设原数为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出错，很容易少几句话...

  1 //以下代码中：加important标记的是曾经缺少的，注释掉的是曾经多的
  2 #include<cstdio>
  3 #include<cstring>
  4 #define lc (num<<1)
  5 #define rc (num<<1|1)
  6 #define mid ((l+r)>>1)
  7 typedef long long LL;
  8 LL a[300100];
  9 LL tree[1200100],laz[1200100],laz2[1200100];
 10 LL L,R,x,n,m,md;
 11 void build(LL l,LL r,LL num)
 12 {
 13     laz2[num]=1;//important
 14     if(l==r)
 15     {
 16         tree[num]=a[l]%md;
 17         return;
 18     }
 19     build(l,mid,lc);
 20     build(mid+1,r,rc);
 21     tree[num]=(tree[lc]+tree[rc])%md;
 22 }
 23 void pushdown(LL l,LL r,LL num)
 24 {
 25     if(laz2[num]!=1)
 26     {
 27         laz2[lc]=(laz2[lc]*laz2[num])%md;
 28         laz2[rc]=(laz2[rc]*laz2[num])%md;
 29         /*important*/
 30         laz[lc]=(laz[lc]*laz2[num])%md;
 31         laz[rc]=(laz[rc]*laz2[num])%md;
 32         tree[lc]=(tree[lc]*laz2[num])%md;
 33         tree[rc]=(tree[rc]*laz2[num])%md;
 34         /*-important*/
 35         /*
 36         tree[lc]=(tree[lc]+(mid-l+1)*laz2[num])%md;
 37         tree[rc]=(tree[rc]+(r-mid)*laz2[num])%md;
 38         */
 39         laz2[num]=1;
 40     }
 41     if(laz[num])
 42     {
 43         laz[lc]=(laz[lc]+laz[num])%md;
 44         laz[rc]=(laz[rc]+laz[num])%md;
 45         tree[lc]=(tree[lc]+(mid-l+1)*laz[num]%md)%md;
 46         tree[rc]=(tree[rc]+(r-mid)*laz[num]%md)%md;
 47         laz[num]=0;
 48     }
 49 }
 50 void update(LL l,LL r,LL num)
 51 {
 52     if(L<=l&&r<=R)
 53     {
 54         tree[num]=(tree[num]+(r-l+1)*x)%md;
 55         laz[num]=(laz[num]+x)%md;
 56         return;
 57     }
 58     pushdown(l,r,num);
 59     if(L<=mid)    update(l,mid,lc);
 60     if(mid<R)    update(mid+1,r,rc);//if(mid+1<=R)//等价
 61     /*important*/tree[num]=(tree[lc]+tree[rc])%md;
 62 }
 63 void update2(LL l,LL r,LL num)
 64 {
 65     if(L<=l&&r<=R)
 66     {
 67         tree[num]=(tree[num]*x)%md;
 68         /*importaant*/laz[num]=(laz[num]*x)%md;/*important*/
 69         laz2[num]=(laz2[num]*x)%md;
 70         return;
 71     }
 72     pushdown(l,r,num);
 73     if(L<=mid)    update2(l,mid,lc);
 74     if(mid<R)    update2(mid+1,r,rc);//if(mid+1<=R)//等价
 75     /*important*/tree[num]=(tree[lc]+tree[rc])%md;
 76 }
 77 LL query(LL l,LL r,LL num)
 78 {
 79     if(L<=l&&r<=R)    return tree[num];
 80     pushdown(l,r,num);
 81     LL ans=0;
 82     if(L<=mid)    ans=(ans+query(l,mid,lc))%md;
 83     if(mid<R)    ans=(ans+query(mid+1,r,rc))%md;
 84     return ans;
 85 }
 86 int main()
 87 {
 88     LL i,t;
 89     scanf("%lld%lld%lld",&n,&m,&md);
 90     for(i=1;i<=n;i++)
 91         scanf("%lld",&a[i]);//不应该将laz2[]=1写在此处important
 92     build(1,n,1);
 93     for(i=1;i<=m;i++)
 94     {
 95         scanf("%lld",&t);
 96         if(t==2)
 97         {
 98             scanf("%lld%lld%lld",&L,&R,&x);
 99             update(1,n,1);
100         }
101         else if(t==3)
102         {
103             scanf("%lld%lld",&L,&R);
104             printf("%lld\n",query(1,n,1)%md);
105         }
106         else
107         {
108             scanf("%lld%lld%lld",&L,&R,&x);
109             update2(1,n,1);
110         }
111     }
112     return 0;
113 }