# 海战（线段树）- HDU 4027

• 线段树的结构为一个二叉树，每个节点都代表一个坐标区间，节点N所代表的区间记为Int(N)，则其需符合以下条件：
• 其每一个叶节点，从左到右代表每个单位区间。
• 其内部节点代表的区间是其两个儿子代表的区间之联集。
• 每个节点（包含叶子）中有一个储存线段的数据结构。若一个线段S的坐标区间包含Int(N)但不包含Int(parent(N))，则节点N中会储存线段S。

Problem Description

A lot of battleships of evil are arranged in a line before the battle. Our commander decides to use our secret weapon to eliminate the battleships. Each of the battleships can be marked a value of endurance. For every attack of our secret weapon, it could decrease the endurance of a consecutive part of battleships by make their endurance to the square root of it original value of endurance. During the series of attack of our secret weapon, the commander wants to evaluate the effect of the weapon, so he asks you for help.

You are asked to answer the queries that the sum of the endurance of a consecutive part of the battleship line.

Notice that the square root operation should be rounded down to integer.

Input

The input contains several test cases, terminated by EOF.

For each test case, the first line contains a single integer N, denoting there are N battleships of evil in a line. (1 <= N <= 100000)

The second line contains N integers Ei, indicating the endurance value of each battleship from the beginning of the line to the end. You can assume that the sum of all endurance value is less than 263.

The next line contains an integer M, denoting the number of actions and queries. (1 <= M <= 100000)

For the following M lines, each line contains three integers T, X and Y. The T=0 denoting the action of the secret weapon, which will decrease the endurance value of the battleships between the X-th and Y-th battleship, inclusive. The T=1 denoting the query of the commander which ask for the sum of the endurance value of the battleship between X-th and Y-th, inclusive.

T=0 表示使用秘密武器攻击一次，X和Y表示区间。

T=1 表示指挥官询问区间X和Y敌舰的生命值总和。

Output

For each test case, print the case number at the first line. Then print one line for each query. And remember follow a blank line after each test case.

Sample Input

10

1 2 3 4 5 6 7 8 9 10

5

0 1 10

1 1 10

1 1 5

0 5 8

1 4 8

Sample Output

Case #1:

19

7

6

G++：690ms

```#include <stdio.h>
#include <math.h>
#define MAXN 100010

//线段树节点
typedef struct node_s {
long long sum;
int l, r, len;
} node_t;

static node_t tree[MAXN * 4];

// 更新统计总生命值
void update_sum(int now) {
//总值为左右孩子的值的和
tree[now].sum = tree[now << 1].sum + tree[now << 1 | 1].sum;
}

//构建区间[l,r]
void build(int now, int l, int r) {
tree[now].l = l;
tree[now].r = r;
tree[now].len = tree[now].r - tree[now].l + 1;

//输入生命值
if (tree[now].l == tree[now].r) {
scanf("%lld", &tree[now].sum);
return;
}

//中间位置
int mid = (tree[now].l + tree[now].r) >> 1;

//更新左右孩子
build(now << 1, l, mid);
build(now << 1 | 1, mid + 1, r);

//计算该节点的值
update_sum(now);
}

//被秘密武器攻击后，需要更新敌舰的生命值
void update(int now, int l, int r) {
//说明生命值全部是1，无需更新
if (tree[now].sum == tree[now].len) return;

//更新战舰生命值
if (tree[now].l == tree[now].r) {
tree[now].sum = (long long)sqrt((double)tree[now].sum);
return;
}

int mid = (tree[now].l + tree[now].r) >> 1;

if (r <= mid) update(now << 1, l, r);
else if (l > mid) update(now << 1 | 1, l, r);
else { update(now << 1, l, mid); update(now << 1 | 1, mid + 1, r); }

update_sum(now);
}

//查询区间[l,r]的总生命值
long long query(int now, int l, int r) {
//如果刚好是这个区间，直接返回，线段树的性能优势在于此
if (tree[now].l == l && tree[now].r == r)
return tree[now].sum;

int mid = (tree[now].l + tree[now].r) >> 1;

if (r <= mid) return query(now << 1, l, r);
else if (l > mid) return query(now << 1 | 1, l, r);

//在两个区间的情况
return query(now << 1, l, mid) + query(now << 1 | 1, mid + 1, r);
}

int main() {
int size, query_count;

int case_num = 0;

while (~scanf("%d", &size)) {
printf("Case #%d:\n", ++case_num);
build(1, 1, size);
scanf("%d", &query_count);

for (int i = 1; i <= query_count; i++) {
int T, X, Y;
scanf("%d%d%d", &T, &X, &Y);

//交换大小
if (X > Y)
X ^= Y, Y ^= X, X ^= Y;

//T=0表示攻击，攻击后需要更新生命值
//T=1表示查询，获取区间的总生命值
if (T == 0)
update(1, X, Y);
else
printf("%lld\n", query(1, X, Y));
}
printf("\n");
}
}```

216 篇文章34 人订阅

0 条评论

## 相关文章

### [LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程，具体内容层次按照{题目，分析，初解，初解结果，优化解，优化解结...

34860

37670

### 枚举

​ 枚举就是尝试所有的可能性，尤其是当我们在确定一个问题是不是的这一类问题中尤其有用，例如说给一堆数，让我我们判断他们是不是素数，或者素数的数量的时候，这...

32160

### 我是如何击败Java自带排序算法的

Java 8 对自带的排序算法进行了很好的优化。对于整形和其他的基本类型， Arrays.sort() 综合利用了双枢轴快速排序、归并排序和启发式插入排序。这个...

13310

36240

50450

### BZOJ 4318: OSU!

Description osu 是一款群众喜闻乐见的休闲软件。  我们可以把osu的规则简化与改编成以下的样子:  一共有n次操作，每次操作只有成功与失败之分，...

37280

40460

329100

45970