描述
南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较,计算出两个人的杀敌数差值,用这种方法一方面能鼓舞杀敌数高的人,另一方面也算是批评杀敌数低的人,起到了很好的效果。
所以,南将军经常问军师小工第i号士兵到第j号士兵中,杀敌数最高的人与杀敌数最低的人之间军功差值是多少。
现在,请你写一个程序,帮小工回答南将军每次的询问吧。
注意,南将军可能询问很多次。
- 输入
只有一组测试数据第一行是两个整数N,Q,其中N表示士兵的总数。Q表示南将军询问的次数。(1<N<=100000,1<Q<=1000000)随后的一行有N个整数Vi(0<=Vi<100000000),分别表示每个人的杀敌数。再之后的Q行,每行有两个正正数m,n,表示南将军询问的是第m号士兵到第n号士兵。 - 输出
对于每次询问,输出第m号士兵到第n号士兵之间所有士兵杀敌数的最大值与最小值的差。 - 样例输入
5 2
1 2 6 9 3
1 2
2 4 - 样例输出
1
7
分析:
刚刚拿到题目的时候习惯性带入以为还是考查树状数组,然后突然意识到是考查的是线段树,还有一点就是因为要求这个区间中的最大值与最小值的差值,原先想的就是直接保存该根节点下的最大值与最小值,但是这样的话你在找到的时候没有办法同时返回这个区间的最大值与最小值,所以另外在结构体中定义一个结构体变量,来存储最大、最小值以及差值。
这样的话找到后可以直接返回该结构体。
代码:
#include<stdio.h>
#include<iostream>
#include<stack>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<algorithm>
using namespace std;
struct Node
{
int Max;///最大值
int Min;///最小值
int Cha;///差值
};
struct Node1
{
int left;///左端点
int right;///右端点
struct Node N;///该区间内的最大值、最小值、以及差值
} node[400009];///线段树
int N,Q;
int a[100009];
struct Node built(int root,int le,int ri)///root根节点,le左端点、ri右端点
{
node[root].left=le;///首先确定该根结点的左右端点
node[root].right=ri;
if(le==ri)///如果左右端点相等的话,相当于找到了最后一层,这个区间只有一个点
{
///分别给该节点下的Node结构体赋值,当前的递归结束
node[root].N.Max=a[le];
node[root].N.Min=a[le];
node[root].N.Cha=0;
return node[root].N;
}
///然后递归构建根节点的左右子树
int mid=(le+ri)/2;
struct Node N1,N2,N3;
N1=built(root*2,le,mid);///左子树
N2=built(root*2+1,mid+1,ri);///右子树
int Min1=min(N1.Min,N2.Min);///选取左右子树中的最值存储到根节点中
int Max1=max(N1.Max,N2.Max);
N3.Max=Max1;
N3.Min=Min1;
N3.Cha=Max1-Min1;
node[root].N=N3;
return N3;
}
struct Node Find(int root,int le,int ri)
{
if(node[root].left==le&&node[root].right==ri)///找到该确定的区间就返回,该区间必须左右端点分别满足才行
{
return node[root].N;
}
else if(ri<=node[root*2].right)///如果该右端点比其左子树的右端点还小,肯定在左子树中找
return Find(root*2,le,ri);
else if(le>=node[root*2+1].left)///如果该左端点比其右子树的左端点还小,肯定在右子树中找
return Find(root*2+1,le,ri);
else
{
int mid=(node[root].left+node[root].right)/2;///也就是相当于有一部分区间在左子树,有一部分区间在右子树
struct Node N1,N2,N3;
N1=Find(root*2,le,mid);///分别找左右子树中的最大、最小值
N2=Find(root*2+1,mid+1,ri);
int Min1=min(N1.Min,N2.Min);
int Max1=max(N1.Max,N2.Max);
N3.Max=Max1;
N3.Min=Min1;
N3.Cha=Max1-Min1;
return N3;
}
}
int main()
{
scanf("%d%d",&N,&Q);
for(int i=1; i<=N; i++)
scanf("%d",&a[i]);
built(1,1,N);///建树
int f,t;
for(int i=0; i<Q; i++)
{
scanf("%d%d",&f,&t);
struct Node NN=Find(1,f,t);///查找
printf("%d\n",NN.Cha);
}
return 0;
}
NYOJ 119 士兵杀敌(三) (线段树)的更多相关文章
-
NYOJ 116 士兵杀敌 (线段树,区间和)
题目链接:NYOJ 116 士兵杀敌 士兵杀敌(二) 时间限制:1000 ms | 内存限制:65535 KB 难度:5 描写叙述 南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的 ...
-
NYOJ 119 士兵杀敌(三) RMQ ST
NYOJ 119 士兵杀敌(三) RMQ ST 题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=119 思路: ST在线 预处理O(nlog ...
-
nyoj 119士兵杀敌(三)(线段树区间最值查询,RMQ算法)
题目119 题目信息 执行结果 本题排行 讨论区 士兵杀敌(三) 时间限制:2000 ms | 内存限制:65535 KB 难度:5 描写叙述 南将军统率着N个士兵,士兵分别编号为1~N,南将军常 ...
-
nyoj 119 士兵杀敌(三)【线段树区间最大值最小值差】
士兵杀敌(三) 时间限制:2000 ms | 内存限制:65535 KB 难度:5 描述 南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进 ...
-
nyoj 119 士兵杀敌(三) 【线段树】【单点更新】
题意:. .. 策略如题. 思路:我们先如果仅仅求某一区间的最大值.我们仅仅须要利用线段树的模板.仅仅须要初始化和询问的时候小小的改动一下.改成祖先结点储存的不再是子节点的和而是两个子节点之间的最大值 ...
-
nyoj 119 士兵杀敌(三)(RMQ)
士兵杀敌(三) 时间限制:2000 ms | 内存限制:65535 KB 难度:5 描述 南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进 ...
-
NYOJ 119 士兵杀敌(三)(RMQ算法)
採用的的是小牛的写法,蒟蒻第一次写.. RMQ (Range Minimum/Maximum Query)问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n).返回数 ...
-
POJ 3264-Balanced Lineup, NYOJ 119-士兵杀敌3 线段树
士兵杀敌(三) 时间限制:2000 ms | 内存限制:65535 KB 难度:5 描述 南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比 ...
-
NYOJ 108 士兵杀敌1(树状数组)
首先,要先讲讲树状数组: 树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构.主要用于查询任意两位之间的所有元素之 ...
随机推荐
-
Git工作流指南:Pull Request工作流
参考地址:http://blog.jobbole.com/76854/ Pull Requests是Bitbucket上方便开发者之间协作的功能.提供了一个用户友好的Web界面,在集成提交的变更到正式 ...
-
Windows下Python工具pip的安装
1.打开pip的文档官网 https://pip.pypa.io/en/stable/ ,进入installation.在installation里,我们需要的是get-pip.py这个脚本. 选中后 ...
-
EJB到底是什么,真的那么神秘吗??
1. 我们不禁要问,什么是"服务集群"?什么是"企业级开发"? 既然说了EJB 是为了"服务集群"和"企业级开发",那么 ...
-
jquery表单验证使用插件formValidator
JQuery表单验证使用插件formValidator 作者: 字体:[增加 减小] 类型:转载 时间:2012-11-10我要评论 jquery表单验证使用插件formValidator,可供有需求 ...
-
[HIHO1300]展胜地的鲤鱼旗(栈,dp)
题目链接:http://hihocoder.com/problemset/problem/1300 给一个字符串,只包含'('和')',问存在多少个子串似的括号是匹配的. 匹配规则在题干中描(蒻)述( ...
-
js 去掉空格
写成类的方法格式如下:(str.trim();)<script language="javascript"> String.prototype.trim=functio ...
-
html页面头部里的meta
作者:zccst html中的http-equiv属性应用详解 一.简介 http-equiv 属性 -- HTTP协议的响应头报文 此属性出现在meta标签中 此属性用于代替name,HTTP服务器 ...
-
论文阅读-attention-is-all-you-need
1结构介绍 是一个seq2seq的任务模型,将输入的时间序列转化为输出的时间序列. 有encoder和decoder两个模块,分别用于编码和解码,结合时是将编码的最后一个输出 当做 解码的第一个模块的 ...
-
C# 插件式开发
在网上找了下插件式编程的资料,这里自己先借鉴下别人的,同时发现有自己的看法,不过由于本人水平有限,不一定有参考价值,写出来一方面是为了总结自己,以求提高,另一方面也希望各为朋友看到我的不足,给我提出宝 ...
-
(转) Rabbitmq学习笔记
详见原文: http://blog.csdn.net/shatty/article/details/9529463 Rabbitmq学习笔记