poj 3468 A Simple Problemwith Integersセグメントツリー遅延更新

A Simple Problem with IntegersTime Limit:5000MS    Memory Limit:131072KB    64bit IO Format:%I64d & %I64u
SubmitStatus
Description
次の2つの質問を処理する必要があるシーケンスが示されています.
「C a b c」は、[a,b]区間に与えられた値がすべてc(−1000≦c≦10000)増加したことを示す.
「Q a b」は、[a,b]区間のすべての値の和を尋ねる.
Input
第1行は2つの整数N,Qを含む.1 ≤ N,Q ≤ 100000.
2行目には、初期シーケンスA(−1000000000≦Ai≦10000000)を表すn個の整数が含まれる.
次のQ行は、タイトルの説明のようにフォーマットされています.
Output
Qの冒頭の質問ごとに、対応する答えを出力し、各答えの行を出力する必要があります.
Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

明らかな線分木の題目は,修正時に区間修正であるため,この修正は単点修正よりも時間がかかるため,遅延更新を用いる必要があり,はっきり言って更新時に1つの区間が満たされている条件を加えると,この区間点の値のみを修正し,そのフラグビットを設定してそのサブ区間が更新されていないことを示す.再更新またはクエリーの場合、サブセクション間で使用する必要があります.再更新します.この遅延は、前回更新されなかった設定の値と、今回更新されなかった設定の値が加算されることに注意してください.

#include <iostream>
#include <stdio.h>
#define maxn 100000
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
using namespace std;
ll add[maxn<<2];//       
ll sum[maxn<<2];

void push_up(ll rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void push_down(ll rt,ll num)//    
{
    if(add[rt])
    {
        add[rt<<1]+=add[rt];//        
        add[rt<<1|1]+=add[rt];
        sum[rt<<1]+=add[rt]*(num-(num>>1));//     
        sum[rt<<1|1]+=add[rt]*(num>>1);
        add[rt]=0;//     
    }
}

void build(ll l,ll r,ll rt)
{
    add[rt]=0;
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        return;
    }
    ll m=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}

void update(ll L,ll R,ll data,ll l,ll r,ll rt)
{
    if(L<=l&&R>=r)
    {
        add[rt]+=data;
        sum[rt]+=data*(r-l+1);
        return;
    }
    push_down(rt,r-l+1);//       ，    
    ll m=(l+r)>>1;
    if(L<=m)
        update(L,R,data,lson);
    if(R>m)
        update(L,R,data,rson);
    push_up(rt);
}

ll query(ll L,ll R,ll l,ll r,ll rt)
{
    if(L<=l&&R>=r)
    {
        return sum[rt];
    }
    push_down(rt,r-l+1);//       ，    
    ll res=0;
    ll m=(l+r)>>1;
    if(L<=m)
        res+=query(L,R,lson);
    if(R>m)
        res+=query(L,R,rson);
    return res;

}



int main()
{
    ll n,q;
    char op[2];
    ll parm[3];
    scanf("%lld%lld",&n,&q);
    build(1,n,1);
    while(q--)
    {
        scanf("%s%lld%lld",op,&parm[0],&parm[1]);
        switch(op[0])
        {
        case 'Q':
            printf("%lld
",query(parm[0],parm[1],1,n,1));
            break;
        case 'C':
            scanf("%lld",&parm[2]);
            update(parm[0],parm[1],parm[2],1,n,1);
            break;
        }
    }
    return 0;
}