`

【线段树 + 简单题】杭电 hdu 1166 敌兵布阵

阅读更多

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
              Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1166
    Name  : 1166 敌兵布阵
    Date  : Sunday, September 18, 2011
    Time Stage : half an hour

    Result: 
4622708	2011-09-18 15:43:38	Accepted	1166
46MS	1764K	2586 B
C++	pyy小号

4622706	2011-09-18 15:43:14	Runtime Error
(ACCESS_VIOLATION)	1166
15MS	1164K	2586 B
C++	pyy小号


    Test Data :

Review :
线段树的感觉,比较麻烦一点,同时空间和时间消耗都比树状数组要大
//----------------------------------------------------------------------------*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>

#define MAXSIZE 50001

typedef struct {
	int left, right ;
	int sum ;
} NODE ;

int		tcase, n ;
NODE	tree[MAXSIZE * 4] ;

void build (int node, int left, int right)
{
	tree[node].left		= left ;
	tree[node].right	= right ;
	tree[node].sum		= 0 ;

	if (left == right) 
		return ;

	int mid = (left + right) / 2 ;
	build (node * 2, left, mid) ;
	build (node * 2 + 1, mid + 1, right) ;
}

void update (int node, int pos, int val)
{
	// 当前区间的总人数增加
	tree[node].sum += val ;

	// 刚好走到第pos 个营地所在的叶子
	if (tree[node].left == pos && 
		tree[node].right == pos)
	{
		return ;
	}

	int mid = (tree[node].left + tree[node].right) / 2 ;
	// 若营地在当前区间的左半边
	if (pos <= mid)
		update (node * 2, pos, val) ;
	// 若营地在当前区间的右半边
	else 
		update (node * 2 + 1, pos, val) ;

	return ;
}

int query (int node, int left, int right)
{
	// 若区间刚好匹配
	if (tree[node].left == left &&
		tree[node].right == right)
		return tree[node].sum ;

	// 若区间无交集
	if (tree[node].left > right ||
		tree[node].right < left)
		return 0 ;

	// 若区间有交集
	int mid = (tree[node].left + tree[node].right) / 2 ;

	// 若查询区间在左半边
	if (right <= mid)
		return query (node * 2, left, right) ;
	// 若查查询区间在右半边
	else if (mid < left)
		return query (node * 2 + 1, left, right) ;
	// 若查询区间横跨当前区间的中点
	else
		return query (node * 2, left, mid) + query (node * 2 + 1, mid + 1, right) ;
}


int main ()
{
	char	str[20] ;
	int		i, j ;
	int		x, y ;

	while (scanf ("%d", &tcase) != EOF)
	{
		for (j = 1 ; j <= tcase ; ++j)
		{
			scanf ("%d", &n) ;
			build (1, 1, n) ;
			for (i = 1 ; i <= n ; ++i)
			{
				scanf ("%d", &x) ;
				// 从根部开始查找,第i 个营地的值增加x
				update (1, i, x) ;
			}
			printf ("Case %d:\n", j) ;
			while (scanf ("%s", str), *str != 'E')
			{
				scanf ("%d%d", &x, &y) ;
				if (*str == 'Q')
					printf ("%d\n", query (1, x, y)) ;
				else if (*str == 'A')
					update (1, x, y) ;
				else if (*str == 'S')
					update (1, x, -y) ;
			}
		}
	}
	return 0 ;
}

分享到:
评论

相关推荐

    【题解】「HDU1166」敌兵布阵(线段树)

    题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...

    杭电HDU ACM培训课件

    《杭电HDU ACM培训课件》是一份珍贵的学习资源,源自杭州电子科技大学的ACM竞赛培训课程。这些课件是官方论坛上分享的,旨在为那些积分不足无法获取资源或者对ACM编程竞赛感兴趣的初学者提供帮助。下面将详细阐述这...

    hdu acm1166线段树

    hdu 1166线段树代码

    hdu 1166线段树

    标题与描述均提到了“hdu 1166线段树”,这表明文章的核心是关于线段树在解决特定问题中的应用。线段树是一种数据结构,主要用于处理区间查询和更新操作,尤其是在大规模数据集上。在本例中,通过分析给定的部分代码...

    杭电HDU2050题的ac程序

    一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了

    ACM hdu 线段树题目+源代码

    ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...

    计算机网络复习大纲_杭电hdu.pdf

    计算机网络复习大纲_杭电hdu.pdf

    计算机网络复习大纲_杭电hdu整理.pdf

    计算机网络复习大纲_杭电hdu整理.pdf

    杭电HDU ACM 1005

    杭电ACM1005题源代码,AC了的程序,无问题……

    计算机网络复习大纲_杭电hdu参考.pdf

    计算机网络复习大纲_杭电hdu参考.pdf

    acm课件简单数学题(杭电)(HDU)

    本课件"acm课件简单数学题(杭电)(HDU)"正是针对这一领域的一份宝贵资源,旨在提升参赛者解决数学问题的能力,从而在ACM竞赛中提高AC(Accepted,即正确解答)题目的效率。 课件中包含的“简单数学题090223.ppt...

    线段树完整版

    **案例2:hdu1166 敌兵布阵** - **功能**: 单点增减与区间求和查询。 - **关键代码解析**: - **PushUp(int rt)**: 同样用于更新父节点的值,在这里是求和。 - **build(int l, int r, int rt)**: 构建线段树。 - ...

    HH神总结的线段树专辑-超经典的

    - 示例题目包括 `hdu1166敌兵布阵` 和 `hdu1754IHateIt`。 - **`hdu1166敌兵布阵`**: - **题意**:给出一个整数序列,支持两种操作:增加某个位置上的数值以及查询某区间内的数值之和。 - **思路**:利用线段...

    杭电操作系统实验 HDU操作系统实验.zip

    杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    线段树入门学习(兼解HDU1754)

    这篇博客“线段树入门学习(兼解HDU1754)”旨在帮助初学者理解线段树的基本概念,并通过解决HDU1754题目来实践其应用。 线段树的核心思想是将一个区间分解成多个子区间,然后对每个子区间进行预处理,存储区间的信息...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

Global site tag (gtag.js) - Google Analytics