HDu敵兵布陣(線分樹の単点更新)

敵兵が布陣する
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 34484    Accepted Submission(s): 14660
Problem Description
C国の死対頭A国はこの間軍事演習を行っていたので、C国のスパイの頭のDerekと彼の部下のTidyはまた忙しくなった.A国は海岸線に沿って直線的にN個の工兵キャンプを配置し、DerekとTidyの任務はこれらの工兵キャンプの活動状況を監視することである.ある種の先進的な監視手段を採用したため、各工兵キャンプの人数C国が把握しているのははっきりしていて、各工兵キャンプの人数が変動する可能性があり、数人の人手を増加したり減らしたりする可能性があるが、これらはC国の監視から逃れられない.中央情報局は敵がどのような戦術を演習しているのかを研究しなければならないので、TidyはいつでもDerekにある連続した工兵キャンプが全部で何人いるかを報告しなければならない.例えば、Derekは「Tidy、すぐに3番目のキャンプから10番目のキャンプまで何人いるかを報告しなさい」と聞いた.Tidyはすぐにこのセグメントの総人数を計算し、報告しなければならない.しかし、敵兵キャンプの人数は常に変動しているが、Derekは尋ねるたびにセグメントが異なるので、Tidyは毎回1つ1つのキャンプの数を数えなければならず、すぐに疲れ果てて、DerekはTidyの計算速度にますます不満を持っている.「自分で計算してみてください.これは本当に疲れた仕事ですね.私はあなたが私を首にするのが嫌いです.」仕方なく、Tidyはコンピュータの専門家Windbreakerに電話して助けを求めるしかありませんでした.Windbreakerは言いました.「肥えた子、普段acmの問題をたくさん作って、アルゴリズムの本をたくさん読んでください.今は苦果を味わったでしょう.」Tidyは言いました.「私は間違っています.....「でもWindbreakerはもう電話を切った.Tidyは悩んでいる.これで彼は本当に崩壊するだろう.賢い読者、プログラムを書いてこの仕事を完成させることができるのか.しかし、プログラムの効率が足りなければ、TidyはDerekに叱られるだろう.
Input
1行目の整数Tは、T組のデータがあることを示す.各組のデータは1行目に正の整数N(N<=50000)があり、敵にN個の工兵キャンプがあることを示し、次にN個の正の整数があり、i個目の正の整数aiは第i個の工兵キャンプの開始時にai人がいることを表す(1<=ai<=50).次に各行に1本の命令があり、命令には4つの形式がある:(1)Add i j,i,jは正の整数であり、i番目のキャンプ増加j個人(jが30を超えない)(2)Sub i j,i,jは正の整数であり、i番目のキャンプ減少j個人(jが30を超えない)を示す.(3)Query i j,i,jは正の整数であり、i<=jであり、iからj番目のキャンプを尋ねる総人数を示す.(4)Endは終了を示し、このコマンドは各グループのデータの最後に現れる.各グループのデータには最大40000のコマンドがある
Output
i番目のグループのデータに対しては、まず「Case i:」とリターンを出力し、Queryごとの問い合わせに対して1つの整数を出力してリターンし、問い合わせのセグメントの総人数を表し、この数はint以内に保たれる.
Sample Input
1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End
Sample Output
Case 1: 6 33 59

#include <cstdio>

#define lson l , m , rt << 1

#define rson m + 1 , r , rt << 1 | 1

const int maxn = 55555;

int sum[maxn*4];



void PushUP(int rt)

{

      sum[rt] = sum[rt * 2] + sum[rt *2 +1];

}



void build(int l,int r,int rt)

{

    if (l == r)

    {

        scanf("%d",&sum[rt]);

        return ;

    }



    int m = (l + r) / 2;

    build(lson);//lson l , m , rt * 2

    build(rson);//rson m + 1 , r , rt * 2 + 1

    PushUP(rt);

}



void update(int p,int add,int l,int r,int rt)

{

    if (l == r)

    {

        sum[rt] += add;

        return ;

    }

    int m = (l + r) / 2;



    if (p <= m)

        update(p , add , lson);

    else

        update(p , add , rson);



    PushUP(rt);

}

int query(int L,int R,int l,int r,int rt)

{

    if (L <= l && r <= R)

    {

        return sum[rt];

    }

    int m = (l + r) / 2;

    int ret = 0;

    if (L <= m)

        ret += query(L , R , lson);

    if (R > m)

        ret += query(L , R , rson);

    return ret;

}

int main()

{

    int T , n;

    scanf("%d",&T);

    for (int cas = 1 ; cas <= T ; cas ++)

    {

        printf("Case %d:
",cas);

        scanf("%d",&n);

        build(1 , n , 1);

        char op[10];



        while (scanf("%s",op))

        {

            if (op[0] == 'E')

                break;

            int a , b;

            scanf("%d%d",&a,&b);



            if (op[0] == 'Q')//Query i j ,i j    ,i<=j，     i  j       ;

                printf("%d
",query(a , b , 1 , n , 1));

            else if (op[0] == 'S')//Sub i j ,i j    ,   i     j  （j   30）;

                update(a , -b , 1 , n , 1);

            else               //Add i j,i j    ,   i     j  （j   30）;

                update(a , b , 1 , n , 1);

        }



    }

    return 0;

}