poj3468 A Simple Problem with Integers 线段树 区间更新 lazy

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 using namespace std;
  5 typedef long long ll;
  6 #define MS(a) memset(a,0,sizeof(a))
  7 #define MP make_pair
  8 #define PB push_back
  9 const int INF = 0x3f3f3f3f;
 10 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 11 inline ll read(){
 12     ll x=0,f=1;char ch=getchar();
 13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 14     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 15     return x*f;
 16 }
 17 //////////////////////////////////////////////////////////////////////////
 18 const int maxn = 1e5+10;
 19 
 20 ll a[maxn];
 21 
 22 struct node{
 23     int l,r;
 24     ll sum,lazy;
 25     void update(ll val){
 26         sum += 1LL * (r-l+1)*val;
 27         lazy += val;
 28     }
 29 }tree[maxn<<2];
 30 
 31 void pushup(int rt){
 32     tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
 33 }
 34 
 35 void pushdown(int rt){
 36     int lazyval = tree[rt].lazy;
 37     if(lazyval){
 38         tree[rt<<1].update(lazyval);
 39         tree[rt<<1|1].update(lazyval);
 40         tree[rt].lazy = 0;
 41     }
 42 }
 43 
 44 void build(int rt, int l, int r){
 45     tree[rt].l = l, tree[rt].r = r;
 46     tree[rt].sum = 0, tree[rt].lazy = 0;
 47     if(l == r){
 48         tree[rt].sum = a[l];
 49     }else{
 50         int mid = (l+r)/2;
 51         build(rt<<1,l,mid);
 52         build(rt<<1|1,mid+1,r);
 53         pushup(rt);
 54     }
 55 }
 56 
 57 void update(int rt,int l,int r,ll val){
 58     int L = tree[rt].l, R = tree[rt].r;
 59     if(l<=L && R<=r){
 60         tree[rt].update(val);
 61     }else{
 62         pushdown(rt);
 63         int mid = (L+R)/2;
 64         if(l <= mid) update(rt<<1,l,r,val);
 65         if(r > mid) update(rt<<1|1,l,r,val);
 66         pushup(rt);
 67     }
 68 }
 69 
 70 ll query(int rt,int l,int r){
 71     int L = tree[rt].l, R = tree[rt].r;
 72     if(l<=L && R<=r){
 73         return tree[rt].sum;
 74     }else{
 75         ll ans = 0;
 76         pushdown(rt);
 77         int mid = (L+R)/2;
 78         if(l<=mid) ans += query(rt<<1,l,r);
 79         if(r>mid) ans += query(rt<<1|1,l,r);
 80         pushup(rt);
 81         return ans;
 82     }
 83 }
 84 int main(){
 85     int n = read(), q = read();
 86     for(int i=1; i<=n; i++)
 87         a[i] = read();
 88     build(1,1,n);
 89     while(q--){
 90         char op; int l,r,va;
 91         scanf(" %c",&op);
 92         if(op == 'Q'){
 93             l=read(),r=read();
 94             printf("%I64d
",query(1,l,r));
 95         }else{
 96             l=read(),r=read(),va=read();
 97             update(1,l,r,va);
 98         }
 99     }
100 
101     return 0;
102 }