/* 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 ;
}
分享到:
相关推荐
hdu 1166线段树代码
杭州电子科技大学ACM培训课件 来自杭电ACM官方论坛 拿来和大家分享一下 想到有些朋友论坛积分不够 现在特地拿来免费供大家下载 希望对ACM初学者能够有所帮助
hdu 1166线段树
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
题面 【题目描述】 有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.pdf
计算机网络复习大纲_杭电hdu借鉴.pdf
计算机网络复习大纲_杭电hdu整理.pdf
杭电ACM1005题源代码,AC了的程序,无问题……
计算机网络复习大纲_杭电hdu参考.pdf
杭电ACMhdu1163
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
杭电hdu acm资料所用杭电的acm题
离线OJ题库(HDU ZJU等,部分有答案),需联网。
HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字
杭电acm 第1090题的.cpp文件