【HDU No. 1166】 敌兵布阵

【HDU No. 1166】 敌兵布阵

杭电 OJ 题目地址

【题意】

A国在海岸线沿直线布置了N 个工兵营地。C国通过先进的监测手段对A国每个工兵营地的人数都掌握得一清二楚。每个工兵营地的人数都可能发生变动，可能增加或减少若干人手。

【输入输出】

输入：

第1行包含一个整数T ，表示有T 组数据。每组数据的第1行都包含一个正整数N （N ≤50000），表示有N 个工兵营地。接下来有N 个正整数，第i 个正整数ai 代表第i 个工兵营地开始时有ai 个人（1≤ai ≤50）。再接下来每行都有一条命令，每组数据最多有40000条命令，命令有4种形式：①Add i j ，表示第i 个营地增加j 个人（j≤30）；②Sub i j ，表示第i 个营地减少j 个人（j ≤30）；③Query i j ，i ≤j ，表示查询第i ～j 个营地的总人数（int以内）；④End，表示结束，在每组数据的最后出现。

命令中的i 和j 均为正整数。

输出：

对第i 组数据，首先单行输出“Case i:”，然后对每个Query都单行输出查询区间的总人数。

【样例】

【思路分析】

这道题包括点更新和区间查询，可以采用树状数组或者线段树解决。

【算法设计】

① 创建线段树，存储区间和。

② 点更新，查询到该点后进行点更新，返回时更新区间和。

③ 区间查询，首先查找该区间，然后返回区间和值。

创建线段树时可以采用存储区间信息和不存储区间信息两种方法，本题采用不存储区间信息的方法创建线段树，并对两种区间查询方法进行对比。

【创建线段树的两种方法】

创建线段树的方法不同，数据结构和区间查询时的参数也不同。

① 节点存储区间信息。每个节点都存储区间信息l 、r ，以及其他信息如最值或和值。在前面线段树的基本操作中就采用了这种方式，进行区间查询时只需3个参数：待查询区间L 、R 和当前节点的编号。

② 节点不存储区间信息。每个节点都不存储区间信息l、r ，用数组存储其他信息如最值或和值。进行区间查询时需要5个参数：待查询区间L 、R ；当前节点的l 、r ；当前节点编号rt 。节点不存储区间信息构建线段树的代码如下，区间查询的代码在后面给出。

#define lson l , m , rt << 1
#define rson m + 1, r, rt << 1 | 1

void build(int l , int r , int rt){ // 构建线段树
	
	if(l == r){
		scanf("%d" , &sum[rt]);
		return;
	}
	
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
	sum[rt] = sum[rt * 2] + sum[rt * 2 + 1]; // 更新区间和
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

【 区间查询的两种方法】

无论采用哪种方法创建线段树，都可以采用区间覆盖和区间相等两种方法进行区间查询。以节点不存储区间信息的5个参数区间和查询为例，3个参数类似。

① 区间覆盖。判断条件为覆盖时，查询区间无须改变，一直是[L , R ]，累加左右两个区间查询的和值。

int query(int L,int R,int l,int r,int rt)//区间查询1
{
    if (L<=l&&r<=R)// 判断条件为覆盖，查询区间[L, R] 覆盖当前节点区间[l ,r]
        return sum[rt];
    int m=(l+r)>>1;
    int ret=0; // 定义变量，分两种情况累加 区间和( 或者求最值)
    if(L<=m) ret+=query(L,R,lson);
    if(R>m) ret+=query(L,R,rson);
    return ret; // 返回结果
}
1
2
3
4
5
6
7
8
9
10

② 区间相等。判断条件为相等且跨两个区间查询时，左右子树的查询范围分别变为[L , m ]、[m +1, R ]。

int query(int L,int R,int l,int r,int rt){//区间查询2
    if(L==l&&r==R)//判断条件为相等，查询区间[L, R] 等于当前节点区间[l ,r]
        return sum[rt];
    int m=(l+r)>>1;
    if(R<=m) // 分三种情况直接返回结果
		return query(L,R,lson);
    else if(L>m)
			return query(L,R,rson);
    	else return query(L,m,lson)+query(m+1,R,rson); // 左右子树查询范围变为[L, m]、 [m + 1 , R]
}
1
2
3
4
5
6
7
8
9
10

【算法实现】

#include
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int maxn=55555;

int sum[maxn<<2];

void PushUP(int rt){//更新和值
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void build(int l,int r,int rt){//构建线段树
    if(l==r){
	    scanf("%d",&sum[rt]);
	    return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUP(rt);
}

void update(int p,int add,int l,int r,int rt){//单点更新
    if (l==r){
        sum[rt]+=add;
        return ;
	}
    int m=(l+r)>>1;
    if(p<=m) update(p,add,lson);
    else update(p,add,rson);
    PushUP(rt);
}


int query(int L,int R,int l,int r,int rt){//区间查询2
    if(L==l&&r==R)//判断条件为相等
        return sum[rt];
    int m=(l+r)>>1;
    if(R<=m)
		return query(L,R,lson);
    else if(L>m)
			return query(L,R,rson);
    	else return query(L,m,lson)+query(m+1,R,rson);
}

int main(){
	
    int T,n;
    scanf("%d",&T);
    
    for (int cas=1;cas<=T;cas++){
    	
        printf("Case %d:\n",cas);
        scanf("%d",&n);
        build(1,n,1);
        char op[10];
        while(scanf("%s",op)){
            if(op[0]=='E') break;
            int i,j;
            scanf("%d%d",&i,&j);
            if(op[0]=='Q') printf("%d\n",query(i,j,1,n,1));
            else if(op[0]=='S') update(i,-j,1,n,1);
                else update(i,j,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