# 09-09 HDU_Steps5.3 树状数组,LCA HDU1166 HDU2492 HDU3584 HDU2586 HDU2874 HDU3486 HDU2688

2016-12-14 09:53:18来源:http://blog.csdn.net/swm8023/article/details/6770841作者:swm8023人点击

5.3.1 HDU1166 敌兵布阵

query[i..j]=sum(j)-sum(i-1)

`#include #include using namespace std;const int MAXN=50010;int n,cas,x,y;char op[6];//树状数组操作int c[MAXN*2];void init(){memset(c,0,sizeof c);}int lowbit(int x){return x&-x;}void modify(int i,int k){while(iint sum(int i){int s=0;while(i>0)s+=c[i],i-=lowbit(i);return s;}//============int main(){	scanf("%d",&cas);	for(int ca=1;ca<=cas;ca++){		init();		scanf("%d",&n);			for(int i=1;i<=n;i++){scanf("%d",&x);modify(i,x);}		printf("Case %d:/n",ca);		while(scanf("%s",op),strcmp(op,"End")){			scanf("%d%d",&x,&y);			if(strcmp(op,"Add")==0)modify(x,y);			else if(strcmp(op,"Sub")==0)modify(x,-y);			else printf("%d/n",sum(y)-sum(x-1));						}	}		}`

5.3.2 HDU2492 Ping Pong

`#include #include #include using namespace std;const int MAXN=20010,MAXA=110010;int cas,n,ai[MAXN];int lmin[MAXN],rmin[MAXN],lmax[MAXN],rmax[MAXN];//每个裁判左右边大/小于他的数的个数//树状数组int c[MAXA*2];void init(){memset(c,0,sizeof c);}int lowbit(int x){return x&-x;}void modify(int x){while(xint sum(int x){int s=0;while(x>0)s+=c[x],x-=lowbit(x);return s;}int main(){	scanf("%d",&cas);	while(cas--){		scanf("%d",&n);		for(int i=1;i<=n;i++)scanf("%d",&ai[i]);		//从左边开始扫描,扫描左边小于(大于)他的		init();		for(int i=1;i<=n;i++){			lmin[i]=sum(ai[i]-1);			lmax[i]=i-lmin[i]-1;			modify(ai[i]);			}		//从右边开始扫描,扫描右边小于(大于)他的			init();		for(int i=n;i>=1;i--){			rmin[i]=sum(ai[i]-1);			rmax[i]=n-i-rmin[i];			modify(ai[i]);			}		__int64 res=0;		for(int i=1;i<=n;i++){			res+=lmin[i]*rmax[i]+lmax[i]*rmin[i];			}		printf("%I64d/n",res);	}	return 0;	}`

5.3.3
HDU3584 Cube

`#include #include using namespace std;const int MAXN=105;/*	三维树状数组	记录(0,0,0)->(x,y,z)这个点的修改次数	使用容斥原理得到(x1,y1,z1)->(x2,y2,z2);	在(x1,y1,z1)处+1,(x2,y2,z2)处-1	%2就能得到结果*/int c[MAXN][MAXN][MAXN];int lowbit(int x){return x&-x;}int modify(int x, int y, int z, int num){	int j, k;	while(x < MAXN){j = y;		while(j < MAXN){k = z;			while(k < MAXN){				c[x][j][k] += num;				k += lowbit(k);			}			j += lowbit(j);		}			x += lowbit(x);	}}int sum(int x,int y,int z){	int s = 0;	int j,k;	while(x > 0){j = y;		while(j > 0){k = z;			while(k > 0){				s += c[x][j][k];				k -= lowbit(k);				}			j -= lowbit(j);		}		x -= lowbit(x);	}	return s;}int main(){	int n,m,op,x1,y1,z1,x2,y2,z2;	while(scanf("%d%d", &n, &m) != EOF){		memset(c, 0, sizeof c);		while(m--){			scanf("%d%d%d%d", &op, &x1, &y1, &z1);			if(op==1){				scanf("%d%d%d", &x2, &y2, &z2);				modify(x1, y1, z1, 1);                modify(x2+1, y1, z1, -1);                modify(x1, y2+1, z1, -1);                modify(x1, y1, z2+1, -1);                modify(x1, y2+1, z2+1, 1);                modify(x2+1, y1, z2+1, 1);                modify(x2+1, y2+1, z1, 1);                modify(x2+1, y2+1, z2+1, -1);			}else{				printf((sum(x1, y1, z1) & 1)?"1/n":"0/n");				}						}	}	return 0;	}`

5.3.4 HDU2586How far away ？

5.3.5 HDU2874Connections between cities

2586比较裸,直接套算法就可以了

2874首先要判断两个点是否连通,这里可以用并查集实现,只有在一个区块中才去查询.

2874的内存比较紧张..注意节省空间..这里贴的是2874的代码

`#include #include #include #include using namespace std;int n,m,c,ans[1000001],hash[10001];//图操作struct edge{	int v,w;	edge(int b,int c){v=b,w=c;}};struct edge2{	int v,ind;	edge2(int b,int c){v=b,ind=c;}};vector ed[10001];vector qr[10001];//并查集int p[10010];int find(int x){return x==p[x]?x:p[x]=find(p[x]);}void merge(int x,int y){p[find(y)]=find(x);}//LCAbool vis[10001];int dis[10001];void LCA_Targin(int u){	vis[u]=1;	for(size_t i=0;i		int v=qr[u][i].v;		if(vis[v])ans[qr[u][i].ind]=dis[u]+dis[v]-2*dis[find(v)];	}	for(size_t i=0;i		int v=ed[u][i].v;		if(!vis[v]){			dis[v]=dis[u]+ed[u][i].w;			LCA_Targin(v);			merge(u,v);		}	}}//初始化void init(){	memset(vis,0,sizeof vis);	memset(hash,0,sizeof hash);		for(int i=0;i<10001;i++){		p[i]=i;		ed[i].clear();qr[i].clear();	}}int main(){	while(scanf("%d%d%d",&n,&m,&c)!=EOF){		init();		int x,y,z;		for(int i=0;i			scanf("%d%d%d",&x,&y,&z);			ed[x].push_back(edge(y,z));			ed[y].push_back(edge(x,z));			merge(x,y);		}					for(int i=0;i			scanf("%d%d",&x,&y);			if(find(x)!=find(y)){//对于不连通的点				ans[i]=-1;continue;				}			qr[x].push_back(edge2(y,i));			qr[y].push_back(edge2(x,i));		}				//添加虚拟根节点,向每个块增加一条连线		for(int i=1;i<=n;i++){			int t=find(i);			if(hash[t]==0){				hash[t]=1;				ed[0].push_back(edge(t,0));				ed[t].push_back(edge(0,0));			}		}							for(int i=0;i<10010;i++)p[i]=i;		dis[0]=0;		LCA_Targin(0);				for(int i=0;i			if(ans[i]==-1)printf("Not connected/n");			else printf("%d/n",ans[i]);			}	}	return 0;	}`

5.3.6 HDU3486Interviewe

`#include using namespace std;const int MAXN=200001;int n,k,v[MAXN];int mmax(int a,int b){return a>b?a:b;}int r;int getmax(int mid){	int rs=0,tk=n/mid;	for(int i=1;i<=mid;i++){		int maxn=-1;		for(int j=tk*(i-1)+1;j<=tk*i;j++)maxn=mmax(v[j],maxn);		rs+=maxn;		if(rs>k){r=mid;return 1;}	}	return 0;}int main(){	while(scanf("%d%d",&n,&k),n!=-1&&k!=-1){		int sum=0;		for(int i=1;i<=n;i++){			scanf("%d",&v[i]);			sum+=v[i];		}		if(sum		else{			int low=1,high=n;			//二分分成的组数			while(low<=high){				int mid=(low+high)/2;				//如果此时组数满足条件,减少组数,否则增加				if(getmax(mid))high=mid-1;				else low=mid+1;			}			printf("%d/n",r);		}	}}`

5.3.7 HDU2688 Rotate

`#include #include using namespace std;typedef __int64 LL;const int MAXN=3000010,MAXA=10010;int n,m,f[MAXN],s,e,tmp,mor,les;LL res;char op,c;LL a[MAXA];int lowbit(int x){return x&-x;}void modify(int x){while(xLL sum(int x){LL s=0;while(x>0)s+=a[x],x-=lowbit(x);return s;}inline void scan(int &x){	while(c=getchar(),c<'0'||c>'9');x=c-'0';	while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';}int main(){	while(scanf("%d",&n)!=EOF){		res=0;		memset(a,0,sizeof a);				for(int i=1;i<=n;i++){			scan(f[i]);			modify(f[i]);			res+=sum(f[i]-1);				}		scan(m);		while(m--){			scanf(" %c",&op);			if(op=='Q'){				printf("%I64d/n",res);				}else if(op=='R'){				scan(s);scan(e);				s++,e++;				if(s>e)tmp=s,s=e,e=tmp;				tmp=f[s],mor=0,les=0;				for(int i=s+1;i<=e;i++){					if(f[i]>tmp)mor++;					else if(f[i]					f[i-1]=f[i];				}				f[e]=tmp;				res+=les-mor;							}			}				}	return 0;	}`

5.3.8 HDU3030 表示没看懂题..贴大牛代码的..罪过..