POJ - 3468(线段树+lazy标记 区间更新 区间查询)

题目：click
题意：Q 查询一段区间，C给一段区间加值。

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<istream>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
#define llinf 0x3f3f3f3f3f3f3f3f
#define MAX_len 100005*4
using namespace std;
typedef long long ll;
#define m ((l+r)>>1)
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
int n;
struct A {
    int l,r;
    ll w,lazy;

}tree[MAX_len];
ll a[100005];
void build_tree(int p,int l1,int r1)
{
    tree[p].l=l1,tree[p].r=r1;
    if(l1==r1)
    {
        tree[p].w=a[l1];
        return ;
    }
    int mid=(l1+r1)>>1;
    build_tree((p<<1),l1,mid);
    build_tree((p*2+1),mid+1,r1);
    tree[p].w=tree[(p<<1)].w+tree[(p<<1)|1].w;
}
void PushDown(int p)
{//下放标记
    if(tree[p].lazy)
    {
        int temp=tree[p*2].r-tree[p*2].l+1;
        tree[p*2].w+=tree[p].lazy*temp;
        temp=tree[p*2+1].r-tree[p*2+1].l+1;
        tree[p*2+1].w+=tree[p].lazy*temp;
        tree[p*2].lazy+=tree[p].lazy;
        tree[p*2+1].lazy+=tree[p].lazy;
        tree[p].lazy=0;
    }
}
void update(int p,int l1,int r1,ll val)
{
    if(tree[p].l>=l1&&tree[p].r<=r1)
    {
        tree[p].w+=val*(tree[p].r-tree[p].l+1);
        tree[p].lazy+=val;
        return ;
    }
    PushDown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(l1<=mid)
    {
        update(p*2,l1,r1,val);
    }
    if(r1>mid)
    {
        update(p*2+1,l1,r1,val);
    }
    tree[p].w=tree[p*2].w+tree[p*2+1].w;
}
ll query(int p,int l1,int r1)
{
    if(l1<=tree[p].l&&r1>=tree[p].r)
    {
        return tree[p].w;
    }
    PushDown(p);
    int mid=(tree[p].l+tree[p].r)/2;
    ll res=0;
    if(l1<=mid)
    {
        res+=query(p*2,l1,r1);
    }
    if(r1>mid)
    {
        res+=query(p*2+1,l1,r1);
    }
    return res;
}
int main()
{
    int i,j,T;
    scanf("%d %d",&n,&T);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build_tree(1,1,n);
    while(T--)
    {
        getchar();
        char temp;
        int x,y;
        temp=getchar();
        scanf("%d %d",&x,&y);
        if(temp=='C')
        {
            ll hh;
            scanf("%lld",&hh);
            update(1,x,y,hh);
        }
        else
        {
            printf("%lld\n",query(1,x,y));
        }
    }
    return 0;
}