hdu 1166 敵兵布陣單點更新+區(qū)間查詢 segment tree or BIT

2019-11-11 02:36:34

字體：大中小

供稿：網(wǎng)友

題目：

敵兵布陣

Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 82428 Accepted Submission(s): 34810PRoblem DescriptionC國的死對頭A國這段時間正在進行軍事演習(xí)，所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。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的責罵的. 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 OutputCase 1:63359
代碼：
①線段樹
#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>#include<ctype.h>    //tower()#include<set>  #include<map>  #include<iomanip>// cout<<setprecision(1)<<fixed<<a;#include<vector>   #include<time.h>  #include<assert.h>  //assert#include<cmath>	#include<algorithm>#include<bitset>#include<limits.h>#include<stack>#include<queue>using namespace std;const int maxn=50010;const int inf=0x7fffffff;/*線段樹單點更新*/#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1int n,t,stree[maxn<<2];//根節(jié)點維護區(qū)間和 char s[7];void build(int l,int r,int rt){//葉節(jié)點從l到r，樹根為rt	if(l==r){		scanf("%d",&stree[rt]);		return;	}	int mid=(l+r)>>1;	build(lson);	build(rson);	stree[rt]=stree[rt<<1]+stree[rt<<1|1]; }void update(int x,int v,int l,int r,int rt){//線段樹（樹根為rt，對應(yīng)區(qū)間為[l,r]）中x結(jié)點加v 	if(l==r){		stree[rt]+=v;		return;	}	int mid=(l+r)>>1;	if(x<=mid) update(x,v,lson);	if(x>mid) update(x,v,rson);	stree[rt]=stree[rt<<1]+stree[rt<<1|1];}int query(int a,int b,int l,int r,int rt){//查詢線段樹（樹根為rt，對應(yīng)區(qū)間為[l,r]）中子區(qū)間[a,b]區(qū)間和 	if(a<=l&&b>=r) return stree[rt];	int ans=0;	int mid=(l+r)>>1;	if(a<=mid) ans+=query(a,b,lson);	if(b>mid) ans+=query(a,b,rson);	return ans;}int main(){//327MS	2356K	scanf("%d",&t);	for(int cas=1;cas<=t;++cas){		printf("Case %d:/n",cas);		scanf("%d",&n);		memset(stree,0,sizeof(stree));		build(1,n,1);		int p,q;		while(~scanf("%s",s)){			if(s[0]=='Q') scanf("%d%d",&p,&q),printf("%d/n",query(p,q,1,n,1));			else if(s[0]=='A') scanf("%d%d",&p,&q),update(p,q,1,n,1);			else if(s[0]=='S') scanf("%d%d",&p,&q),update(p,-q,1,n,1);			else if(s[0]=='E') break;		}	}	return 0;}
②樹狀數(shù)組
#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>#include<ctype.h>    //tower()#include<set>  #include<map>  #include<iomanip>// cout<<setprecision(1)<<fixed<<a;#include<vector>   #include<time.h>  #include<assert.h>  //assert#include<cmath>	#include<algorithm>#include<bitset>#include<limits.h>#include<stack>#include<queue>using namespace std;const int maxn=50010;const int inf=0x7fffffff;int n,t,c[maxn];char s[7];int sum(int i){	int s=0;	while(i>0){		s+=c[i];		i-=i&(-i);	}	return s;}void add(int i,int x){	while(i<=n){//n not maxn		c[i]+=x;		i+=i&(-i);	}}int main(){//312MS	1768K	int a,p,q;	scanf("%d",&t);	for(int cas=1;cas<=t;++cas){		memset(c,0,sizeof(c));		printf("Case %d:/n",cas);		scanf("%d",&n);		for(int i=1;i<=n;++i){			scanf("%d",&a);			add(i,a);		}		while(~scanf("%s",s)){			if(s[0]=='Q') scanf("%d%d",&p,&q),printf("%d/n",sum(q)-sum(p-1));			else if(s[0]=='A') scanf("%d%d",&p,&q),add(p,q);			else if(s[0]=='S') scanf("%d%d",&p,&q),add(p,-q);			else if(s[0]=='E') break;		}	}	return 0;}