線分樹:敵兵布陣

A-敵兵布陣
Time Limit:1000MS    Memory Limit:32768KB    64bit IO Format:%I64d & %I64u
Submit
Status
Practice
HDU 1166
Description
C国の死対頭A国はこの間軍事演習を行っていたので、C国のスパイの頭のDerekと彼の部下のTidyはまた忙しくなった.A国は海岸線に沿って直線的にN個の工兵キャンプを配置し、DerekとTidyの任務はこれらの工兵キャンプの活動状況を監視することである.ある種の先進的な監視手段を採用したため、各工兵キャンプの人数C国が把握しているのははっきりしていて、各工兵キャンプの人数が変動する可能性があり、数人の人手を増加したり減らしたりする可能性があるが、これらはC国の監視から逃れられない.
中央情報局は敵がどのような戦術を演習しているのかを研究しなければならないので、TidyはいつでもDerekにある連続した工兵キャンプが全部で何人いるかを報告しなければならない.例えば、Derekは「Tidy、すぐに3番目のキャンプから10番目のキャンプまで何人いるかを報告しなさい」と聞いた.Tidyはすぐにこの段落の総人数を計算して報告しなければならない.しかし、敵兵キャンプの人数は常に変動し、Derekは尋ねるたびにセグメントが異なるので、Tidyは毎回1つずつキャンプの数を数えなければならず、すぐに疲れ果ててしまいました.DerekはTidyの計算速度にますます不満を持っています:“あなたは死んで太っていて、計算がこんなに遅いので、私はあなたを首にします!”Tidyは考えます:“あなたは自分で計算してみて、これは本当に疲れた仕事です!私はあなたが私を首にすることを憎んでいます!”仕方なく、Tidyはコンピュータの専門家Windbreakerに電話して助けを求めるしかなかった.Windbreakerは言った.「死んだデブ、普段acmの問題をたくさん作って、アルゴリズムの本をたくさん読んで、今は苦果を味わったでしょう.」ティディは「私は間違っていることを知っています...」と言った.しかし、Windbreakerはもう電話を切った.Tidyは悩んでいます.これで彼は本当に崩壊します.賢い読者、プログラムを書いて彼にこの仕事を完成させることができますか.しかし、プログラムの効率が足りなければ、TidyはDerekに叱られます.
 
Input
1行目の整数Tは、Tグループのデータがあることを示す.
各グループのデータの最初の行には正の整数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は終了を示し、このコマンドは各グループのデータの最後に現れる.
データのセットあたり最大4,000個のコマンド
 
Output
i番目のグループのデータに対して、まず「Case i:」とリターンを出力し、
Queryクエリごとに整数を出力して車に戻り、クエリのセグメントの合計数を表します.この数は最大1000000を超えません.
 
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>
#include <cstring>
#include <cstdio>
#include <string>
#include <iostream>

using namespace std;

char com[100];
int a[50010];
int n;

struct Node{
    int l, r, v;
}tree[200010];

void Build(int pos, int l, int r){
    tree[pos].l = l;
    tree[pos].r = r;
    if(l == r){
        tree[pos].v = a[tree[pos].l];
        return ;
    }
    int mid = (l + r) / 2;
    Build(pos * 2, l, mid);
    Build(pos * 2 + 1, mid + 1, r);
    tree[pos].v = tree[pos * 2].v + tree[pos * 2 + 1].v;
}

void Update(int pos, int idx, int val){
    if(tree[pos].l == tree[pos].r){
        tree[pos].v += val;
        return ;
    }
    int mid = (tree[pos].l + tree[pos].r) / 2;
    if(idx <= mid)
        Update(pos * 2, idx, val);
    else
        Update(pos * 2 + 1, idx, val);
    tree[pos].v = tree[pos * 2].v + tree[pos * 2 + 1].v;
}

int Query(int pos, int l, int r){
    if(l <= tree[pos].l && tree[pos].r <= r){
        return tree[pos].v;
    }
    int ret = 0, mid = (tree[pos].l + tree[pos].r) / 2;
    if(l <= mid)
        ret += Query(pos * 2, l, r);
    if(r > mid)
        ret += Query(pos * 2 + 1, l, r);
    return ret;
}

int main(){
    int t;
    int x, y, i, j, k;
    int cnt = 0;
    scanf("%d", &t);
    while(t --){
        cnt ++;
        scanf("%d", &n);
        printf("Case %d:
", cnt);
        for(i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        Build(1, 1, n);
        while(scanf ("%s", com)){
            if(com[0] == 'E')
                break;
            else if(com[0] == 'Q'){
                scanf("%d%d", &x, &y);
                printf("%d
", Query(1, x, y));
            }
            else if(com[0] == 'A'){
                scanf("%d%d", &x, &y);
                Update(1, x, y);
            }
            else if(com[0] == 'S'){
                scanf("%d%d", &x, &y);
                Update(1, x, -y);
            }
        }
    }
    return 0;
}