poj 3468セグメントツリーセグメント更新

タイトル:
n個の数を与えて、mの中で操作します!!エリアの和はすでにエリアの更新を求めました!
解法:
線分樹!!

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100010;
#define ll long long
ll sum[maxn<<2],col[maxn<<2],s[maxn];
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
void pushUP(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r)
{
    col[rt]=0;
    if(l==r)
    {
        sum[rt]=s[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    pushUP(rt);
}
void pushDOWN(int rt,int m)
{
    if(col[rt])
    {
        col[rt<<1]+=col[rt];
        col[rt<<1|1]+=col[rt];
        sum[rt<<1]+=col[rt]*(m-(m>>1));
        sum[rt<<1|1]+=col[rt]*(m>>1);
        col[rt]=0;
       // pushUP(rt);
    }
}
void updata(int rt,int l,int r,int L,int R,int c)
{
    if(L<=l&&r<=R)
    {
        col[rt]+=c;
        sum[rt]+=(r-l+1)*(ll)c;
        return;
    }
    pushDOWN(rt,r-l+1);//  
    int mid=(l+r)>>1;
    if(mid>=L) updata(lson,L,R,c);
    if(mid<R) updata(rson,L,R,c);
    pushUP(rt);
}
ll query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        return sum[rt];
    }
    pushDOWN(rt,r-l+1);// pushDown  WA  // 

    int mid=(l+r)>>1;
    __int64 res=0;
    if(mid>=L) res+=query(lson,L,R);
    if(mid<R)  res+=query(rson,L,R);
    return res;
}
int main()
{
    int i,j,a,b,c;
    int n,m;
    char op[2];
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++)scanf("%lld",&s[i]);//  ll  WA 
    build(1,1,n);
    while(m--)
    {
       scanf("%s",op);
		if (op[0] == 'Q') {
			scanf("%d%d",&a,&b);
			printf("%lld
",query(1,1,n,a,b));
		} else {
			scanf("%d%d%d",&a,&b,&c);
			updata(1,1,n,a,b,c);
		}
    }
    return 0;
}