海战(线段树)- HDU 4027

这一篇是典型的线段树算法,这个算法在日常工作中可能非常少见,因为可以被常规算法所取代,但是在问题达到一定数量级之后,常规算法是很难搞定类似问题的,可以说线段树是高级算法中非常低调的一种,也许在某些关键时刻能让你化险为夷。

线段树简单的说就是对一个序列每次从中间划分为2个区间,然后依次划分子区间。如图:

先看下维基百科的说明:

线段树(英语:Segment tree)是一种二叉树形数据结构,1977年由Jon Louis Bentley发明[1],用以储存区间或线段,并且允许快速查询结构内包含某一点的所有区间

一个包含n个区间的线段树,空间复杂度O(nlogn),查询的时间复杂度则O(logn+k),其中k是符合条件的区间数量。

此数据结构亦可推广到高维度。

本处以一维的线段树为例。

线段树结构示意,其储存的线段显示在图片的下方。

令S是一维线段的集合。将这些线段的端点坐标由小到大排序,令其为x1,x2,...xn。我们将被这些端点切分的每一个区间称为“单位区间”(每个端点所在的位置会单独成为一个单位区间),从左到右包含:

  • 线段树的结构为一个二叉树,每个节点都代表一个坐标区间,节点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.

注意开根号后需要floor到整值。

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.

输入包含多个用例,使用EOF结束。

对于每个用例,第一行是一个整数N,表示有N个战舰。

第二行包含N个整数Ei,表示每艘战舰的生命值,所有的生命值加起来少于2的63次方。

下面一行包含整数M,表示有多少次攻击或者询问。

接下来有M行,每行包括三个整数T、X、Y。

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");
    }
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-03-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专注数据中心高性能网络技术研发

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

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

34860
来自专栏Python小屋

最快的组合数算法之Python实现

原理:以Cni(8,3)为例,按定义式将其展开为(8*7*6*5*4*3*2*1)/(3*2*1)/(5*4*3*2*1),对于8到6之间的数,分子上出现一次而...

37670
来自专栏Java 源码分析

枚举

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

32160
来自专栏java一日一条

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

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

13310
来自专栏编程之旅

数据结构——最小生成树(C++和Java实现)

快要一整个月没有更新博客了,之前的几周每周都想着要写,但是最后时间还是排不开,最近的状态是一直在写代码,一直在怼工作的需求,顺便刷刷算法题,国庆则是没心没肺的玩...

36240
来自专栏深度学习之tensorflow实战篇

稀疏矩阵压缩sparse.csr_matrix函数与sparse.csc_matric详解

概述 在用python进行科学运算时,常常需要把一个稀疏的np.array压缩,这时候就用到scipy库中的sparse.csr_matrix(csr:Comp...

50450
来自专栏数据结构与算法

BZOJ 4318: OSU!

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

37280
来自专栏CDA数据分析师

开工大吉:几个让你月薪3万+的excel神技能

来源:运营圈信息流广告 职场中经常会用到哪些函数? IF函数、SUMIF函数、VLOOKUP函数、SUMPRODUCT函数...... 小编总结了8个在工作中常...

40460
来自专栏数据科学与人工智能

【Python环境】Python自然语言处理系列(1)

一:python基础,自然语言概念 from nltk.book import* 1,text1.concordance("monstrous") 用语...

329100
来自专栏程序员宝库

用 PHP 的方式实现的各类算法合集

项目地址: https://github.com/PuShaoWei/arithmetic-php About 如果说各种编程语言是程序员的招式,那么数据结构和...

45970

扫码关注云+社区

领取腾讯云代金券