首页 > 代码库 > HDU 1166 - 敌兵布阵
HDU 1166 - 敌兵布阵
嗯,这是一道被放在线段树里的树状数组题。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define MAXN 50000+5 5 #define M 30*40000+100 6 using namespace std; 7 int n,a[MAXN],c[30*40000+100]; 8 int lowbit(int x){return x&(-x);} 9 void add(int i,int val) 10 { 11 while(i<=M) 12 { 13 c[i]+=val; 14 i+=lowbit(i); 15 } 16 } 17 int sum(int i) 18 { 19 int s=0; 20 while(i>0) 21 { 22 s+=c[i]; 23 i-=lowbit(i); 24 } 25 return s; 26 } 27 char op[6]; 28 int main() 29 { 30 int t; 31 cin>>t; 32 for(int kase=1;kase<=t;kase++) 33 { 34 scanf("%d",&n); 35 memset(c,0,sizeof(c)); 36 for(int i=1;i<=n;i++){ 37 scanf("%d",&a[i]); 38 add(i,a[i]); 39 } 40 printf("Case %d:\n",kase); 41 while(scanf("%s",op)) 42 { 43 if(op[0]==‘E‘) break; 44 if(op[0]==‘Q‘) 45 { 46 int l,r; 47 scanf("%d%d",&l,&r); 48 printf("%d\n",sum(r)-sum(l-1)); 49 } 50 else if(op[0]==‘A‘) 51 { 52 int pos,x; 53 scanf("%d%d",&pos,&x); 54 add(pos,x); 55 } 56 else if(op[0]==‘S‘) 57 { 58 int pos,x; 59 scanf("%d%d",&pos,&x); 60 add(pos,-x); 61 } 62 } 63 } 64 }
当然还是得用线段树做一遍的:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define MAXN 50000+5 5 using namespace std; 6 int n,a[MAXN]; 7 struct Node{ 8 int l,r; 9 int sum,lazy; 10 void update(int x) 11 { 12 sum+=(r-l+1)*x; 13 lazy+=x; 14 } 15 }node[4*MAXN]; 16 void pushdown(int root) 17 { 18 if(node[root].lazy) 19 { 20 node[root*2].update(node[root].lazy); 21 node[root*2+1].update(node[root].lazy); 22 node[root].lazy=0; 23 } 24 } 25 void pushup(int root) 26 { 27 node[root].sum=node[root*2].sum+node[root*2+1].sum; 28 } 29 void build(int root,int l,int r) 30 { 31 node[root].l=l; node[root].r=r; 32 node[root].sum=0; node[root].lazy=0; 33 if(l==r) node[root].sum=a[l]; 34 else 35 { 36 int mid=l+(r-l)/2; 37 build(root*2,l,mid); 38 build(root*2+1,mid+1,r); 39 pushup(root); 40 } 41 } 42 void update(int root,int st,int ed,int val) 43 { 44 if(st>node[root].r || ed<node[root].l) return; 45 if(st<=node[root].l && node[root].r<=ed) node[root].update(val); 46 else 47 { 48 pushdown(root); 49 update(root*2,st,ed,val); 50 update(root*2+1,st,ed,val); 51 pushup(root); 52 } 53 } 54 int query(int root,int st,int ed) 55 { 56 if(ed<node[root].l || node[root].r<st) return 0; 57 if(st<=node[root].l && node[root].r<=ed) return node[root].sum; 58 else 59 { 60 int ans=0; 61 pushdown(root); 62 ans+=query(root*2,st,ed); 63 ans+=query(root*2+1,st,ed); 64 pushup(root); 65 return ans; 66 } 67 } 68 char op[6]; 69 int main() 70 { 71 int t; 72 cin>>t; 73 for(int kase=1;kase<=t;kase++) 74 { 75 scanf("%d",&n); 76 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 77 build(1,1,n); 78 printf("Case %d:\n",kase); 79 while(scanf("%s",op)) 80 { 81 if(op[0]==‘E‘) break; 82 if(op[0]==‘Q‘) 83 { 84 int l,r; 85 scanf("%d%d",&l,&r); 86 printf("%d\n",query(1,l,r)); 87 } 88 else if(op[0]==‘A‘) 89 { 90 int pos,x; 91 scanf("%d%d",&pos,&x); 92 update(1,pos,pos,x); 93 } 94 else if(op[0]==‘S‘) 95 { 96 int pos,x; 97 scanf("%d%d",&pos,&x); 98 update(1,pos,pos,-x); 99 } 100 } 101 } 102 }
这里可以看出线段树和树状数组的速度比较:
HDU 1166 - 敌兵布阵
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。