线段树lazy标记1

描述

给定一个正整数序列A，要求支持以下操作
1）： + a b c 表示在[a，b]上加上一个常数C。
2）： * a b c 在[a，b]上乘上一个常数K。
3）： QUERY a b 查询[a，b]的sum。

输入

第一行两个正整数n、m，n表示序列长度，m表示操作数
第二行n个正整数，第i表示A[i]的大小
接下来的m行，每行有且仅有一种操作，具体和题目描述一致?
n,m<=100000
其他权值都<=50000
小心爆int

输出

对于每个询问操作，输出答案对1000000007取余的结果

样例

输入

10 10
50 14 20 18 19 11 43 43 26 44
+ 3 6 41
QUERY 1 2
+ 5 5 14
QUERY 1 3
QUERY 4 4
QUERY 2 6
* 3 5 31
* 4 8 20
* 5 8 28
QUERY 6 7

输出

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