敵兵布陣

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 36121????Accepted Submission(s): 15282

Problem Description C國的死對頭A國這段時間正在進行軍事演習，所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。A國在海岸線沿直線布置了N個工兵營地,Derek和Tidy的任務就是要監(jiān)視這些工兵營地的活動情況。由于采取了某種先進的監(jiān)測手段，所以每個工兵營地的人數(shù)C國都掌握的一清二楚,每個工兵營地的人數(shù)都有可能發(fā)生變動，可能增加或減少若干人手,但這些都逃不過C國的監(jiān)視。
中央情報局要研究敵人究竟演習什么戰(zhàn)術,所以Tidy要隨時向Derek匯報某一段連續(xù)的工兵營地一共有多少人,例如Derek問:“Tidy,馬上匯報第3個營地到第10個營地共有多少人!”Tidy就要馬上開始計算這一段的總人數(shù)并匯報。但敵兵營地的人數(shù)經(jīng)常變動，而Derek每次詢問的段都不一樣，所以Tidy不得不每次都一個一個營地的去數(shù)，很快就精疲力盡了，Derek對Tidy的計算速度越來越不滿:"你個死肥仔，算得這么慢，我炒你魷魚!”Tidy想：“你自己來算算看，這可真是一項累人的工作!我恨不得你炒我魷魚呢!”無奈之下，Tidy只好打電話向計算機專家Windbreaker求救,Windbreaker說：“死肥仔，叫你平時做多點acm題和看多點算法書，現(xiàn)在嘗到苦果了吧!”Tidy說："我知錯了。。。"但Windbreaker已經(jīng)掛掉電話了。Tidy很苦惱，這么算他真的會崩潰的，聰明的讀者，你能寫個程序幫他完成這項工作嗎？不過如果你的程序效率不夠高的話，Tidy還是會受到Derek的責罵的.

?

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個營地的總人數(shù);
(4)End 表示結束，這條命令在每組數(shù)據(jù)最后出現(xiàn);
每組數(shù)據(jù)最多有40000條命令

?

Output 對第i組數(shù)據(jù),首先輸出“Case i:”和回車,
對于每個Query詢問，輸出一個整數(shù)并回車,表示詢問的段中的總人數(shù),這個數(shù)保持在int以內(nèi)。

?

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

?

Author Windbreaker

?

Recommend Eddy???|???We have carefully selected several similar problems for you:??1542?1540?1255?2795?1828?

?

1 //328MS 1984K 1515 B G++ 2 /* 3 4 模板題. 5 6 */ 7 #include<stdio.h> 8 #include<string.h> 9 #define N 50005 10 int p[N]; 11 struct node{ 12 int l,r; 13 int num; 14 }tree[4*N]; 15 void build(int l,int r,int id) //構圖 16 { 17 tree[id].l=l; 18 tree[id].r=r; 19 if(l==r){ 20 tree[id].num=p[l];return; 21 } 22 int mid=(l+r)>>1; 23 build(l,mid,2*id); 24 build(mid+1,r,2*id+1); 25 tree[id].num=tree[2*id].num+tree[2*id+1].num; 26 } 27 void update(int x,int change,int id) //更新 28 { 29 if(tree[id].l==x && tree[id].r==x){ 30 tree[id].num+=change;return; 31 } 32 int mid=(tree[id].l+tree[id].r)>>1; 33 if(x<=mid) update(x,change,2*id); 34 else update(x,change,2*id+1); 35 tree[id].num=tree[2*id].num+tree[2*id+1].num; 36 } 37 int query(int l,int r,int id) //查詢 38 { 39 if(tree[id].l>=l && tree[id].r<=r){ 40 return tree[id].num; 41 } 42 int mid=(tree[id].l+tree[id].r)>>1; 43 if(mid<l) return query(l,r,2*id+1); 44 else if(mid>=r) return query(l,r,2*id); 45 else return query(l,mid,2*id)+query(mid+1,r,2*id+1); 46 } 47 int main(void) 48 { 49 int t,n,k=1; 50 int a,b; 51 char op[10]; 52 scanf("%d",&t); 53 while(t--) 54 { 55 scanf("%d",&n); 56 for(int i=1;i<=n;i++) scanf("%d",&p[i]); 57 build(1,n,1); 58 printf("Case %d:\n",k++); 59 while(scanf("%s",op)){ 60 if(strcmp(op,"End")==0) break; 61 scanf("%d%d",&a,&b); 62 if(op[0]=='A') update(a,b,1); 63 else if(op[0]=='S') update(a,-b,1); 64 else printf("%d\n",query(a,b,1)); 65 } 66 } 67 return 0; 68 }

?

?

加 樹狀數(shù)組法：

1 //281MS 640K 996 B G++ 2 /* 3 4 樹狀數(shù)組法： 5 用樹狀數(shù)組比線段樹更簡潔，代碼較少，理解也簡單點。 6 a[i]記錄每個點的初始值。 7 c[i]記錄某段的和。 8 模板題。 9 10 */ 11 #include<stdio.h> 12 #include<string.h> 13 #define N 50005 14 int a[N],c[N]; 15 int lowbit(int i) 16 { 17 return i&(-i); 18 } 19 void update(int k,int detal) 20 { 21 for(;k<N;k+=lowbit(k)) 22 c[k]+=detal; 23 } 24 int getsum(int k) 25 { 26 int t=0; 27 for(;k>0;k-=lowbit(k)) 28 t+=c[k]; 29 return t; 30 } 31 int main(void) 32 { 33 int t,n,x,y,k=1; 34 char op[10]; 35 scanf("%d",&t); 36 while(t--) 37 { 38 scanf("%d",&n); 39 memset(c,0,sizeof(c)); 40 memset(a,0,sizeof(a)); 41 for(int i=1;i<=n;i++){ 42 scanf("%d",&a[i]); 43 update(i,a[i]); 44 } 45 printf("Case %d:\n",k++); 46 while(scanf("%s",op)){ 47 if(strcmp(op,"End")==0) break; 48 scanf("%d%d",&x,&y); 49 if(op[0]=='Q'){ 50 printf("%d\n",getsum(y)-getsum(x-1)); 51 }else if(op[0]=='A'){ 52 update(x,y); 53 }else{ 54 update(x,-y); 55 } 56 } 57 } 58 return 0; 59 }

?

轉載于:https://www.cnblogs.com/GO-NO-1/p/3627705.html

總結

以上是生活随笔為你收集整理的hdu 1166 敌兵布阵 (线段树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。