线段树——区间累加、区间累乘、区间求和

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 const int maxn=1e5+5;
  5 int n,a[maxn],q,mod;
  6 struct node
  7 {
  8     int l,r;
  9     ll sum,add_lazy,mul_lazy;
 10     void update(int mul,int add)
 11     {
 12         sum=(sum*mul*1ll+add*1ll*(r-l+1))%mod;
 13         mul_lazy=(mul_lazy*mul)%mod;
 14         add_lazy=(add_lazy*mul+add)%mod;
 15     }
 16 }tree[maxn<<2];
 17 
 18 void push_up(int x)
 19 {
 20     tree[x].sum=(tree[x<<1].sum+tree[x<<1|1].sum)%mod;
 21 }
 22 void push_down(int x)
 23 {
 24     int mul=tree[x].mul_lazy;
 25     int add=tree[x].add_lazy;
 26     if(mul!=1 || add!=0)
 27     {
 28         tree[x<<1].update(mul,add);
 29         tree[x<<1|1].update(mul,add);
 30         tree[x].add_lazy=0;
 31         tree[x].mul_lazy=1;
 32     }
 33 }
 34 void build(int x,int l,int r)
 35 {
 36     tree[x].l=l,tree[x].r=r;
 37     tree[x].add_lazy=tree[x].sum=0;
 38     tree[x].mul_lazy=1;
 39     if(l==r)
 40     {
 41         tree[x].sum=a[l];
 42     }
 43     else
 44     {
 45         int mid=(l+r)>>1;
 46         build(x<<1,l,mid);
 47         build(x<<1|1,mid+1,r);
 48         push_up(x);
 49     }
 50 }
 51 void update(int x,int l,int r,ll val,int flag)
 52 {
 53     int L=tree[x].l,R=tree[x].r;
 54 
 55     if(l<=L && R<=r)
 56     {
 57         if(flag==1)tree[x].update(val,0);
 58         else tree[x].update(1,val);
 59     }
 60     else
 61     {
 62         push_down(x);
 63         int mid=(L+R)>>1;
 64         if(mid>=l)update(x<<1,l,r,val,flag);
 65         if(mid<r)update(x<<1|1,l,r,val,flag);
 66         push_up(x);
 67     }
 68 }
 69 ll query(int x,int l,int r)
 70 {
 71     int L=tree[x].l,R=tree[x].r;
 72 
 73     if(l<=L && R<=r)
 74     {
 75         return tree[x].sum%mod;
 76     }
 77     else
 78     {
 79         push_down(x);
 80         ll ans=0;
 81         int mid=(L+R)>>1;
 82         if(mid>=l)ans+=query(x<<1,l,r)%mod;
 83         if(mid<r)ans+=query(x<<1|1,l,r)%mod;
 84         push_up(x);
 85         return ans%mod;
 86     }
 87 
 88 }
 89 int main()
 90 {
 91     scanf("%d%d%d",&n,&q,&mod);
 92     for(int i=1;i<=n;i++)
 93         scanf("%d",&a[i]);
 94     build(1,1,n);
 95     for(int i=1;i<=q;i++)
 96     {
 97         int l,r,op;
 98         ll val;
 99         scanf("%d",&op);
100         if(op==1)
101         {
102             scanf("%d%d%lld",&l,&r,&val);
103             update(1,l,r,val,op);
104         }
105         else if(op==2)
106         {
107             scanf("%d%d%lld",&l,&r,&val);
108             update(1,l,r,val,op);
109         }
110         else
111         {
112             scanf("%d%d",&l,&r);
113             printf("%lld\n",query(1,l,r));
114         }
115 
116 
117     }
118     return 0;
119 }