敵兵布陣
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 64143 Accepted Submission(s): 27036Problem Description C國的死對頭A國這段時間正在進行軍事演習(xí)，所以C國間諜頭子Derek和他手下Tidy又開始忙乎了，
hdu1166 敵兵布陣（線段樹）
。A國在海岸線沿直線布置了N個工兵營地,Derek和Tidy的任務(wù)就是要監(jiān)視這些工兵營地的活動情況。由于采取了某種先進的監(jiān)測手段，所以每個工兵營地的人數(shù)C國都掌握的一清二楚,每個工兵營地的人數(shù)都有可能發(fā)生變動，可能增加或減少若干人手,但這些都逃不過C國的監(jiān)視。中央情報局要研究敵人究竟演習(xí)什么戰(zhàn)術(shù),所以Tidy要隨時向Derek匯報某一段連續(xù)的工兵營地一共有多少人,例如Derek問:“Tidy,馬上匯報第3個營地到第10個營地共有多少人!”Tidy就要馬上開始計算這一段的總?cè)藬?shù)并匯報。但敵兵營地的人數(shù)經(jīng)常變動，而Derek每次詢問的段都不一樣，所以Tidy不得不每次都一個一個營地的去數(shù)，很快就精疲力盡了，Derek對Tidy的計算速度越來越不滿:"你個死肥仔，算得這么慢，我炒你魷魚!”Tidy想：“你自己來算算看，這可真是一項累人的工作!我恨不得你炒我魷魚呢!”無奈之下，Tidy只好打電話向計算機專家Windbreaker求救,Windbreaker說：“死肥仔，叫你平時做多點acm題和看多點算法書，現(xiàn)在嘗到苦果了吧!”Tidy說："我知錯了。。。"但Windbreaker已經(jīng)掛掉電話了。Tidy很苦惱，這么算他真的會崩潰的，聰明的讀者，你能寫個程序幫他完成這項工作嗎？不過如果你的程序效率不夠高的話，Tidy還是會受到Derek的責(zé)罵的.
Input 第一行一個整數(shù)T，表示有T組數(shù)據(jù)。
每組數(shù)據(jù)第一行一個正整數(shù)N（N<=50000）,表示敵人有N個工兵營地，接下來有N個正整數(shù),第i個正整數(shù)ai代表第i個工兵營地里開始時有ai個人（1<=ai<=50）。
接下來每行有一條命令，命令有4種形式：
(1) Add i j,i和j為正整數(shù),表示第i個營地增加j個人（j不超過30）
(2)Sub i j ,i和j為正整數(shù),表示第i個營地減少j個人（j不超過30）;
(3)Query i j ,i和j為正整數(shù),i<=j，表示詢問第i到第j個營地的總?cè)藬?shù);
(4)End 表示結(jié)束，這條命令在每組數(shù)據(jù)最后出現(xiàn);
每組數(shù)據(jù)最多有40000條命令
Output 對第i組數(shù)據(jù),首先輸出“Case i:”和回車,
對于每個Query詢問，輸出一個整數(shù)并回車,表示詢問的段中的總?cè)藬?shù),這個數(shù)保持在int以內(nèi)。
Sample Input
1101 2 3 4 5 6 7 8 9 10Query 1 3Add 3 6Query 2 7Sub 10 2Add 6 3Query 3 10End
Sample Output
Case 1:63359
Author Windbreaker
分析：最基礎(chǔ)的線段樹入門題，屬于模板題，每次更新節(jié)點就行了。
#include<iostream>#include<cstdio>#include<cstring>#include<stack>#include<queue>#include<map>#include<set>#include<vector>#include<cmath>#include using namespace std;const double eps = 1e-6;const double pi = acos(-1.0);const int INF = 0x3f3f3f3f;const int MOD = 1000000007;#define ll long long#define CL(a,b) memset(a,b,sizeof(a))#define MAXN 100010struct node{ int a,b,sum;}t[400010];int ans, r[500010];void build(int x, int y, int num){ t[num].a = x; t[num].b = y; if(x == y) t[num].sum = r[y]; else { int mid = (x+y)/2; build(x, mid, num*2); build(mid+1, y, num*2+1); t[num].sum = t[num*2].sum + t[num*2+1].sum; }}void add(int x, int y, int num){ if(t[num].a == x && t[num].b == x) { t[num].sum += y; return ; } int mid = (t[num].a+t[num].b)/2; if(x > mid) add(x, y, num*2+1); else add(x, y, num*2); t[num].sum = t[num*2].sum + t[num*2+1].sum;}void sub(int x, int y, int num){ if(t[num].a == x && t[num].b == x) { t[num].sum -= y; return ; } int mid = (t[num].a+t[num].b)/2; if(x > mid) sub(x, y, num*2+1); else sub(x, y, num*2); t[num].sum = t[num*2].sum + t[num*2+1].sum;}void query(int x, int y, int num){ if(t[num].a == x && t[num].b == y) { ans += t[num].sum; return ; } int mid = (t[num].a+t[num].b)/2; if(y <= mid) query(x, y, num*2); else if(x >= mid+1) query(x, y, num*2+1); else { query(x, mid, num*2); query(mid+1, y, num*2+1); }}int main(){ int T,n; char str[6]; scanf("%d",&T); for(int cas=1; cas<=T; cas++) { int x,y; scanf("%d",&n); r[0] = 0; for(int i=1; i<=n; i++) scanf("%d",&r[i]); build(1, n, 1); printf("Case %d:\n",cas); while(scanf("%s",str)==1) { //scanf("%d%d",&x,&y); if(strcmp(str, "End")==0) break; else if(strcmp(str, "Add")==0) { scanf("%d%d",&x,&y); add(x, y, 1); } else if(strcmp(str, "Sub")==0) { scanf("%d%d",&x,&y); sub(x, y, 1); } else if(strcmp(str, "Query")==0) { scanf("%d%d",&x,&y); ans = 0; query(x, y, 1); printf("%d\n",ans); } } } return 0;}</cmath></vector></set></map></queue></stack></cstring></cstdio></iostream>