[HDU 1166] 敌兵布阵 [HDU 1166] 敌兵布阵

51 阅读 0 评论 34 点赞

我是靠谱客的博主小巧斑马，最近开发中收集的这篇文章主要介绍[HDU 1166] 敌兵布阵 [HDU 1166] 敌兵布阵，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

[HDU 1166] 敌兵布阵

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166

一个线段树区间求和的模板题了。


1 #include<iostream>

2 #include<cstdio>

3 #include<cstring>

4 using namespace std;

5

6 #define MID(l,r) (l+r)>>1

7 #define lson root<<1

8 #define rson root<<1|1

9
 10 const int maxn=5e4+5;
 11 struct Tree
 12 {
 13
int l,r;
 14
int sum;
 15 }tree[maxn*3];
 16
 17 int arr[maxn],ans;
 18
 19 void Build(int root,int l,int r)
 20 {
 21
tree[root].l=l;
 22
tree[root].r=r;
 23
if(l==r)
 24
tree[root].sum=arr[l];
 25
else
 26 
{
 27
int mid=MID(l,r);
 28 
Build(lson,l,mid);
 29
Build(rson,mid+1,r);
 30
tree[root].sum=tree[lson].sum+tree[rson].sum;
 31 
}
 32 }
 33
 34 void Query(int root,int x,int y)
 35 {
 36
if(x<=tree[root].l&&y>=tree[root].r)
 37
ans+=tree[root].sum;
 38
else
 39 
{
 40
int mid=MID(tree[root].l,tree[root].r);
 41
if(x>mid)
 42 
{
 43 
Query(rson,x,y);
 44 
}
 45
else if(y<=mid)
 46 
{
 47 
Query(lson,x,y);
 48 
}
 49
else
 50 
{
 51 
Query(lson,x,y);
 52 
Query(rson,x,y);
 53 
}
 54 
}
 55 }
 56
 57 void Update(int root,int x,int y)
 58 {
 59
tree[root].sum+=y;
 60
if(tree[root].l==x&&tree[root].r==x)
 61
return ;
 62
int mid=MID(tree[root].l,tree[root].r);
 63
if(x>mid)
 64 
Update(rson,x,y);
 65
else
 66 
Update(lson,x,y);
 67
 68 }
 69
 70 int main()
 71 {
 72
int T;
 73
cin>>T;
 74
for(int flag=1;flag<=T;flag++)
 75 
{
 76
int n;
 77
cin>>n;
 78
for(int i=1;i<=n;i++)
 79
scanf("%d",&arr[i]);
 80
Build(1,1,n);
 81
printf("Case %d:n",flag);
 82
char s[10];
 83
while(scanf("%s",s)!=EOF)
 84 
{
 85
if(strcmp(s,"End")==0)
 86
break;
 87
else if(strcmp(s,"Add")==0)
 88 
{
 89
int x,y;
 90
scanf("%d%d",&x,&y);
 91
Update(1,x,y);
 92 
}
 93
else if(strcmp(s,"Sub")==0)
 94 
{
 95
int x,y;
 96
scanf("%d%d",&x,&y);
 97
Update(1,x,-y);
 98 
}
 99
else if(strcmp(s,"Query")==0)
100 
{
101
int x,y;
102
scanf("%d%d",&x,&y);
103
ans=0;
104
Query(1,x,y);
105
printf("%dn",ans);
106 
}
107 
}
108 
}
109
return 0;
110 }