首页 > 代码库 > HDU 1166 敌兵布阵
HDU 1166 敌兵布阵
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166
思路:线段树入门题。
代码:
#include <iostream>#include <cstring>#define MAXSIZE 500000using namespace std;struct node{ int l,r; int sum;}tree[MAXSIZE*4];int num[MAXSIZE];void build(int root,int l,int r){ tree[root].r = r; tree[root].l = l; if(l==r) { tree[root].sum = num[l]; return; } int mid = (r+l)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); tree[root].sum = tree[root*2].sum + tree[root*2+1].sum;}void update(int root,int pos,int value){ if(tree[root].r==tree[root].l&&tree[root].r==pos) { tree[root].sum+=value; return; } int mid = (tree[root].r+tree[root].l)/2; if(pos<=mid) { update(root*2,pos,value); } else { update(root*2+1,pos,value); } tree[root].sum = tree[root*2].sum + tree[root*2+1].sum;}int query(int root,int l,int r){ if(r>=tree[root].r&&l<=tree[root].l) return tree[root].sum; int mid = (tree[root].r+tree[root].l)/2; if(r<=mid) { return query(root*2,l,r); } else if(l>mid) { return query(root*2+1,l,r); } else { int a = query(root*2,l,mid); int b = query(root*2+1,mid+1,r); return a+b; }}int main(){ int test; int n; char t[8]; scanf("%d",&test); int a,b;// freopen("data.txt","r",stdin); for(int k=1;k<=test;k++) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",num+i); } build(1,1,n); printf("Case %d:\n",k); while(scanf("%s",t)&&strcmp(t,"End")!=0) { scanf("%d %d",&a,&b); if(strcmp(t,"Query")==0) { printf("%d\n",query(1,a,b)); } else if(strcmp(t,"Add")==0) { update(1,a,b); } else if(strcmp(t,"Sub")==0) { update(1,a,-b); } } } return 0;}
HDU 1166 敌兵布阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。