hdu 1166——敌兵布阵 （线段树）

本文主要是介绍hdu 1166——敌兵布阵 （线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基础线段树

#include<cstdio>
#include<iostream>
using namespace std;struct Node
{int l,r;int sum;int Mid(){return (l+r)/2;}
}tree[50010*4];void build(int rt,int left,int right)
{tree[rt].l=left;tree[rt].r=right;if(left!=right){int mid=tree[rt].Mid();build(rt*2,left,mid);build(rt*2+1,mid+1,right);tree[rt].sum=tree[2*rt].sum+tree[rt*2+1].sum;	}elsescanf("%d",&tree[rt].sum);
}void Add(int rt,int x,int y)
{tree[rt].sum+=y;if(tree[rt].l==tree[rt].r)return ;int mid=tree[rt].Mid();if(x<=mid)Add(rt*2,x,y);elseAdd(rt*2+1,x,y);
}void Query(int &ans,int rt,int x,int y)
{if(x<=tree[rt].l&&y>=tree[rt].r){ans+=tree[rt].sum;	return ;}int mid=tree[rt].Mid();if(y<=mid)Query(ans,rt*2,x,y);else{if(x>mid)Query(ans,rt*2+1,x,y);else{Query(ans,rt*2,x,mid);Query(ans,rt*2+1,mid+1,y);}}}int main()
{int count=1;int t;int n;scanf("%d",&t);while(t--){printf("Case %d:\n",count++);scanf("%d",&n);build(1,1,n);char str[100];while(scanf("%s",str)){if(str[0]=='E')break;int x,y;scanf("%d%d",&x,&y);if(str[0]=='A')Add(1,x,y);if(str[0]=='S')Add(1,x,-y);if(str[0]=='Q'){int ans=0;Query(ans,1,x,y);printf("%d\n",ans);}}}
}

这篇关于hdu 1166——敌兵布阵 （线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---