POJ 3264 Balanced Lineup 线段树

2024-03-02 09:38
文章标签 poj 线段 balanced 3264 lineup

本文主要是介绍POJ 3264 Balanced Lineup 线段树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

A - Balanced Lineup

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 ≤ ABN), 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

 

题意就是找出区间内最大值最小值之差,刚学线段树,就拿这道题练了练手,代码有些繁琐。

看视频学的线段树,https://www.bilibili.com/video/av9350697?t=814

#include<stdio.h>
#include<iostream>
using namespace std;
struct node{
int left,right,value,small;//value最大  small最小
bool ex;//一开始做的时候最小值好多出现0  为了避免,当二叉树中存在该节点时才对其进行比较
};
int max(int x,int y)
{return x>y?x:y;
}
int min(int x,int y)
{if(x==0)return y;else if(y==0)return x;elsereturn x<y?x:y;}
node tree[200005];//50000  到二叉树里得开4*50000,完全二叉树2*50000
int  height [50005];
void build_tree(int i,int le,int ri)//建树 初始化 
{tree[i].left=le;tree[i].right=ri;tree[i].value=0;tree[i].small=0;tree[i].ex=true;if(le==ri){tree[i].value=height[le];tree[i].small=height[le];return ;}build_tree(i<<1,le,(le+ri)>>1);build_tree((i<<1)+1,((le+ri)>>1)+1,ri);
}
int MAX;
int MIN;
void query(int i,int left,int right)//查找函数
{if(right==tree[i].right&&left==tree[i].left){MAX=max(tree[i].value,MAX);MIN=min(tree[i].small,MIN);return ;}i=i<<1;if(left<=tree[i].right){if(right<=tree[i].right)query(i,left,right);elsequery(i,left,tree[i].right);}i=i+1;if(right>=tree[i].left){if(left>=tree[i].left)query(i,left,right);elsequery(i,tree[i].left,right);}
}
int main()
{
int N,Q;
int i;
int j,k;
cin>>N>>Q;for(i=0;i<100005;i++)tree[i].ex=false;
for(i=1;i<=N;i++)
{scanf("%d",&height[i]);
}
build_tree(1,1,N);
for(i=4*N-1;i>=1;i=i-2)
{if(tree[i].ex==true&&tree[i-1].ex==true&&tree[i/2].ex==true&&(tree[i].small!=0||tree[i-1].small!=0)){tree[i/2].value=max( tree[i].value,tree[i-1].value);tree[i/2].small=min( tree[i].small,tree[i-1].small);}}//因为只有二叉树叶子value和small有值,所以更新对他们父节点赋值
int x,y;for(i=1;i<=Q;i++)
{MAX=0;MIN=10000005;
scanf("%d%d",&x,&y);
query(1,x,y);
printf("%d\n",-MIN+MAX);}return 0;
}

 

这篇关于POJ 3264 Balanced Lineup 线段树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/765696

相关文章

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D