HDU-1166 敌兵布阵（线段树模板题）

95 阅读 0 评论 63 点赞

我是靠谱客的博主犹豫山水，这篇文章主要介绍HDU-1166 敌兵布阵（线段树模板题），现在分享给大家，希望可以做个参考。

N - 敌兵布阵

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Submit Status

Description

Lily 特别喜欢养花，但是由于她的花特别多，所以照料这些花就变得不太容易。她把她的花依次排成一行，每盆花都有一个美观值。如果Lily把某盆花照料的好的话，这盆花的美观值就会上升，如果照料的不好的话，这盆花的美观值就会下降。有时，Lily想知道某段连续的花的美观值之和是多少，但是，Lily的算术不是很好，你能快速地告诉她结果吗？

Input

复制代码

1
2
3
4
5
6
7
8
第一行一个整数T，表示有T组测试数据。
每组测试数据的第一行为一个正整数N(N<=50000)，表示Lily有N盆花。接下来有N个正整数，第i个正整数ai表示第i盆花的初始美观值(1<=ai<=50)。
接下来每行有一条命令，命令有4种形式：
（1）Add i j, i和j为正整数，表示第i盆花被照料的好，美观值增加j(j<=30)
（2）Sub i j, i和j为正整数，表示第i盆花被照料的不好，美观值减少j(j<=30)
（3）Query i j, i和j为正整数，i<=j，表示询问第i盆花到第j盆花的美观值之和
（4）End，表示结束，这条命令在每组数据最后出现
每组数据的命令不超过40000条

复制代码

Output

复制代码

1
2
对于第i组数据，首先输出"Case i:"和回车。
对于每个"Query i j"命令，输出第i盆花到第j盆花的美观值之和。

Sample Input

1
9
 7 9 8 4 4 5 4 2 7
 Query 7 9
 Add 4 9
 Query 3 6
 Sub 9 6
 Sub 3 3
 Query 1 9
 End

复制代码

Sample Output

Case 1:
133050

复制代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include<algorithm>
using namespace std;
int sum[200005];
void build(int l,int r,int rt)//线段树的创建
{//l和r表示该节点线段树的左端点和右端点，rt表示该节点的编号（线段树是完全二叉树，rt*2和rt*2+1既是该节点的两个子节点）
int m;
if(l==r)//如果一个节点的去见识[a,b]，那么他的两个子节点就为[a,x]和[x,b]（a<=x<=b）
{
scanf("%d",&sum[rt]);
return ;
}
m=(l+r)/2;
build(l,m,rt*2);
build(m+1,r,rt*2+1);
sum[rt]=sum[rt*2]+sum[rt*2+1];
}
int query(int L,int R,int l,int r,int rt)//线段树的查询
{//L和R表示要查询的[L,R]区间的值
int m,ans;
if(l>=L && r<=R)
return sum[rt];
m=(l+r)/2;
ans=0;
if(L<=m)
ans+=query(L,R,l,m,rt*2);
if(R>=m+1)
ans+=query(L,R,m+1,r,rt*2+1);
return ans;
}
void updata(int p,int add,int l,int r,int rt)
{//*p和add表示p点的值上升add*/
int m;
if(l==r)
{
sum[rt]+=add;
return;
}
m=(l+r)/2;
if(p<=m)
updata(p,add,l,m,rt*2);
else
updata(p,add,m+1,r,rt*2+1);
sum[rt]=sum[rt*2]+sum[rt*2+1];
}
int
main()
{
int T,n,a,b,cas;
char op[11];
cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
build(1,n,1);
printf("Case %d:n",cas++);
while(scanf("%s",op),op[0]!='E')
{
scanf("%d%d",&a,&b);
if(op[0]=='Q')
printf("%dn",query(a,b,1,n,1));
else if(op[0]=='S')
updata(a,-b,1,n,1);
else
updata(a,b,1,n,1);
}
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include<algorithm>
using namespace std;
int sum[200005];
void build(int l,int r,int rt)//线段树的创建
{//l和r表示该节点线段树的左端点和右端点，rt表示该节点的编号（线段树是完全二叉树，rt*2和rt*2+1既是该节点的两个子节点）
int m;
if(l==r)//如果一个节点的去见识[a,b]，那么他的两个子节点就为[a,x]和[x,b]（a<=x<=b）
{
scanf("%d",&sum[rt]);
return ;
}
m=(l+r)/2;
build(l,m,rt*2);
build(m+1,r,rt*2+1);
sum[rt]=sum[rt*2]+sum[rt*2+1];
}
int query(int L,int R,int l,int r,int rt)//线段树的查询
{//L和R表示要查询的[L,R]区间的值
int m,ans;
if(l>=L && r<=R)
return sum[rt];
m=(l+r)/2;
ans=0;
if(L<=m)
ans+=query(L,R,l,m,rt*2);
if(R>=m+1)
ans+=query(L,R,m+1,r,rt*2+1);
return ans;
}
void updata(int p,int add,int l,int r,int rt)
{//*p和add表示p点的值上升add*/
int m;
if(l==r)
{
sum[rt]+=add;
return;
}
m=(l+r)/2;
if(p<=m)
updata(p,add,l,m,rt*2);
else
updata(p,add,m+1,r,rt*2+1);
sum[rt]=sum[rt*2]+sum[rt*2+1];
}
int
main()
{
int T,n,a,b,cas;
char op[11];
cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
build(1,n,1);
printf("Case %d:n",cas++);
while(scanf("%s",op),op[0]!='E')
{
scanf("%d%d",&a,&b);
if(op[0]=='Q')
printf("%dn",query(a,b,1,n,1));
else if(op[0]=='S')
updata(a,-b,1,n,1);
else
updata(a,b,1,n,1);
}
}
return 0;
}