线段树lazy标记2

描述

给定一个正整数序列A，要求支持以下操作
1）： ADD a b c 表示在[a，b]上加上一个常数C。
2）： COVER 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

输出

对于每个询问操作，输出答案

样例

输入

10 10
17 18 16 12 13 7 13 6 11 20
QUERY 5 6
QUERY 2 7
ADD 1 6 13
QUERY 4 10
ADD 2 5 18
COVER 2 8 11
ADD 6 9 5
QUERY 8 8
ADD 6 9 18
QUERY 5 7

输出

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