好贷网好贷款

HDU 1166 敌兵布阵

发布时间:2016-12-3 23:40:51 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 1166 敌兵布阵",主要涉及到HDU 1166 敌兵布阵方面的内容,对于HDU 1166 敌兵布阵感兴趣的同学可以参考一下。

转载请注明出处:http://blog.csdn.net/a1dark 分析:线段树模板、学的时候画图分析、尽量不要看别人的模板、自己去分析、懂了原理然后自己把它写出来相当有成就感、其实也就是创建、更新和查询操作而已、说难也不难、 #include<stdio.h> #define N 50005 struct node{ int l,r; int sum; }tree[N<<2]; int a[N]; int ans,n; void create(int x,int l,int r){ tree[x].l=l; tree[x].r=r; if(l==r){ tree[x].sum=a[l]; return; } int mid=(l+r)/2; create(x*2,l,mid); create(x*2+1,mid+1,r); tree[x].sum=tree[x*2].sum+tree[x*2+1].sum; } void update(int x,int p,int num){ int l=tree[x].l; int r=tree[x].r; int mid=(l+r)/2; if(l==r){ tree[x].sum+=num; return; } if(p<=mid) update(x*2,p,num); else update(x*2+1,p,num); tree[x].sum=tree[x*2].sum+tree[x*2+1].sum; } void query(int x,int l,int r){ if(tree[x].l==l&&tree[x].r==r){ ans+=tree[x].sum; return; } int mid=(tree[x].l+tree[x].r)/2; if(r<=mid) query(x*2,l,r); else if(l>mid) query(x*2+1,l,r); else{ query(x*2,l,mid); query(x*2+1,mid+1,r); } } int main(){ int t,x,y,k=1; char str[10]; scanf("%d",&t); while(t--){ printf("Case %d:\n",k);k++; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); create(1,1,n); while(scanf("%s",str)){ if(str[0]=='E')break; if(str[0]=='A'){ scanf("%d%d",&x,&y); update(1,x,y); } if(str[0]=='S'){ scanf("%d%d",&x,&y); update(1,x,-y); } if(str[0]=='Q'){ ans=0; scanf("%d%d",&x,&y); query(1,x,y); printf("%d\n",ans); } } } return 0; }

上一篇:LeetCode - Valid Parentheses
下一篇:Android Handler:主线程如何通知子线程

相关文章

相关评论