Balanced Lineup
Time Limit: 5000MS |
|
Memory Limit: 65536K |
Total Submissions: 16163 |
|
Accepted: 7468 |
Case Time Limit: 2000MS |
Description
For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.
Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.
Input
Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.
Output
Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.
Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
Source
题意很简单,就不翻译了。
此题数据量非常大,简单的模拟必然会超时,线段树是个不错的选择
我们可以通过线段树分别查找区间最大值和区间最小值,之差就是答案了。。
Source Code
Problem: 3264
|
|
User: bingshen
|
Memory: 2384K |
|
Time: 1954MS |
Language: C++ |
|
Result: Accepted
|
-
Source Code
#include<stdio.h>
#include<string.h>
struct node
{
int max;
int min;
int l;
int r;
};
node tree[200000];
int h[50005];
int max,min;
int MAX(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int MIN(int a,int b)
{
if(a>b)
return b;
else
return a;
}
void build(int l,int r,int root)
{
tree[root].l=l;
tree[root].r=r;
if(l==r)
{
tree[root].max=h[l];
tree[root].min=h[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,root*2);
build(mid+1,r,root*2+1);
tree[root].max=MAX(tree[2*root].max,tree[2*root+1].max);
tree[root].min=MIN(tree[2*root].min,tree[2*root+1].min);
}
void findmax(int l,int r,int root)
{
if(tree[root].l==l&&tree[root].r==r)
{
if(tree[root].max>max)
max=tree[root].max;
return;
}
int mid=(tree[root].l+tree[root].r)>>1;
if(mid>=r)
findmax(l,r,root*2);
else if(mid<l)
findmax(l,r,root*2+1);
else
{
findmax(l,mid,root*2);
findmax(mid+1,r,root*2+1);
}
}
void findmin(int l,int r,int root)
{
if(tree[root].l==l&&tree[root].r==r)
{
if(tree[root].min<min)
min=tree[root].min;
return;
}
int mid=(tree[root].l+tree[root].r)>>1;
if(mid>=r)
findmin(l,r,root*2);
else if(mid<l)
findmin(l,r,root*2+1);
else
{
findmin(l,mid,root*2);
findmin(mid+1,r,root*2+1);
}
}
int main()
{
int n,q,i,a,b;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)
scanf("%d",&h[i]);
build(1,n,1);
while(q--)
{
max=0;
min=99999999;
scanf("%d%d",&a,&b);
findmax(a,b,1);
findmin(a,b,1);
printf("%d/n",max-min);
}
return 0;
}
-
果断的1Y,很久没这个感觉了。。
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1740501
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
NULL 博文链接:https://128kj.iteye.com/blog/1746750
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2763 程序 线段树 LCA 2000MS AC
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
POJ题解 个人写法 线段树每个人都不一样
POJ3468,线段树处理,注意longlongint
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
此为本人在poj做过的经典题目的代码与一些经典数据结构算法的模板程序,如线段树,拓扑排序等
以每个星星为中心,得到可以罩住它的矩形的左下角的范围,这些范围内的点增加星星亮度,由于落在框上的点不算,框不一定要整数起点,可另左下落在框上算。求亮度和最大的点即可。...每次用线段树更新和求最大值。
acm code of 20053565 poj onlinejudge 高精度 DP 图论 算法 最大流 最小生成树 线段树
POJ 2182 引自余立功《算法训练教程》,线段树的应用