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

www.MyException.Cn  网友分享于：2013-11-16  浏览：0次

"); $("#cnblogs_post_body").prepend(" ");$("#cnblogs_post_body").prepend("

"); //$("#deng4").after(" ");$("#backTop").click(function () { var speed=500;//滑动的速度 $('body,html').animate({ scrollTop: 0 }, speed); return false; });}); //$("body").append("

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

  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 }