hdu 1166 敌兵布阵 线段树(单点更新)

发布时间:2016-12-8 12:12:53 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 1166 敌兵布阵 线段树(单点更新)",主要涉及到hdu 1166 敌兵布阵 线段树(单点更新)方面的内容,对于hdu 1166 敌兵布阵 线段树(单点更新)感兴趣的同学可以参考一下。

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166 题意:中文题,不多说了。 思路:这题以前用树状数组做过,这次用的线段树,当做可参考模板。 代码: #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stack> #include<vector> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) #define maxn 100000 #define INF 1<<25 #define MAX 0x7fffffff typedef long long ll; using namespace std; int n,m,l,r; struct line { int left,right; int n; int value; } a [maxn*4]; void build_tree(int l,int r,int step) { a[step].left=l; a[step].right=r; a[step].n=0; if(l==r) { scanf("%d",&a[step].value); return; } int mid=(l+r)/2; build_tree(l,mid,step*2); build_tree(mid+1,r,step*2+1); a[step].value=a[step*2].value+a[step*2+1].value; } int ans; void add(int s,int step,int k) { if(s==a[step].left&&s==a[step].right) { a[step].value+=k; return; } if(a[step].left==a[step].right) return; int mid=(a[step].left+a[step].right)/2; if(mid>=s) add(s,step*2,k); else if(mid<s) add(s,step*2+1,k); else { add(s,step*2,k); add(s,step*2+1,k); } a[step].value=a[step*2].value+a[step*2+1].value; } int query(int s,int t,int step) { if(a[step].left>=s&&a[step].right<=t) { ans+=a[step].value; return 0; } else { int mid=(a[step].left+a[step].right)/2; if(mid>=t) query(s,t,step*2); else if(mid<s) query(s,t,step*2+1); else { query(s,t,step*2); query(s,t,step*2+1); } } } int main() { int tot,tt; char ss[10]; scanf("%d",&tot); for(int ii=1; ii<=tot; ii++) { memset(a,0,sizeof(a)); scanf("%d",&tt); build_tree(1,tt,1); printf("Case %d:\n",ii); while(scanf("%s",ss)&&ss[0]!='E') { int i,j; scanf("%d%d",&i,&j); if(ss[0]=='A') { add(i,1,j); } else if(ss[0]=='S') { add(i,1,-j); } else if(ss[0]=='Q') { ans=0; query(i,j,1); printf("%d\n",ans); } } } }

上一篇:使用CreatePatternBrush,用位图填充一个矩形区域,出现交错问题??
下一篇:美国Ivanpah太阳能发电站:飞经这里的鸟都被烧焦了

相关文章

相关评论