POJ3264 Balanced Lineup 线段树|ST表

2024-08-28 00:38

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

Balanced Lineup
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 39453 Accepted: 18511
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
两种解法:
一,
最基础的线段树入门题:没有修改。
线段树知识点①:用全局变量更新结果时,只需要在包含时更新,然后根据区间中点m判断是否向左后向右走

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;const int maxn=50000+10;
int Max[maxn*4],Min[maxn*4];void pushUp(int k){Max[k]=max(Max[k*2],Max[k*2+1]);Min[k]=min(Min[k*2],Min[k*2+1]);
}void build(int k,int l,int r){if(l==r){int x;scanf("%d",&x);Max[k]=Min[k]=x;return ;}int m=(l+r)/2;build(k*2,l,m);build(k*2+1,m+1,r);pushUp(k);
}int maxv,minv;void ask(int a,int b,int k,int l,int r){if(a<=l && r<=b){maxv=max(maxv,Max[k]);minv=min(minv,Min[k]);return ;}int m=(l+r)/2;if(a<=m)ask(a,b,k*2,l,m);if(b>m)ask(a,b,k*2+1,m+1,r);
}int main()
{int i,j,res,n,q;scanf("%d%d",&n,&q);build(1,1,n);while(q--){int a,b;scanf("%d%d",&a,&b);if(a>b){int t=a;a=b;b=t;}maxv=-1,minv=1000000+1;ask(a,b,1,1,n);printf("%d\n",maxv-minv);}return 0;
}

二、
SparseTable(ST表)
简练地总结ST算法:
f[i,j]表示以i为起点,区间长度为2^j的区间最值,此时区间为[i,i + 2^j - 1]。
②求f[i,j]时,将其分成两等份,即f[i][j-1],f[i+2^(j-1)][j-1],得f[i,j]=min(f[i][j-1],f[i+2^(j-1)][j-1])
初始态为:f[i][0]=a[i];
求f[i][j]时就采用递推,顺序是:先求区间长度为1的,再求长度为2的,再求长度为4的,即:
先求f[0][1],f[1][1],f[2][1],..,f[n][1],再求f[1][2],f[2][2],f[3][2],...,f[m][2]..,之后求f[1][3],f[2][3],...,f[k][3]
③查询时,将查询区间[a,b]分成两个可能重叠但一定能完全覆盖[a,b]的区间,即从a往后找一段,从b往前找一段,这两段的最值即答案。ans=min(f[a,k],f[b-2^k+1][k]),k为区间长度的log
②是预处理:O(nlogn) ③是查询:O(1)
具体的见:http://blog.csdn.net/insistgogo/article/details/9929103

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;const int maxn=50000+10;
int a[maxn],fax[maxn][21],fin[maxn][21],n;void Init(){int i,j,k;for(i=0;i<n;i++)fax[i][0]=fin[i][0]=a[i];k=int(log(double(n))/log(2.0));for(j=1;j<=k;j++)for(i=0;i<n;i++)if(i+(1<<j)-1<n){fax[i][j]=max(fax[i][j-1],fax[i+(1<<(j-1))][j-1]);fin[i][j]=min(fin[i][j-1],fin[i+(1<<(j-1))][j-1]);}
}int cal(int l,int r){int k=(int)(log((double)(r-l+1))/(log(2.0)));int maxv=max(fax[l][k],fax[r-(1<<k)+1][k]);int minv=min(fin[l][k],fin[r-(1<<k)+1][k]);return maxv-minv;
}int main()
{int x,y,i,q;scanf("%d%d",&n,&q);for(i=0;i<n;i++)scanf("%d",&a[i]);Init();while(q--){scanf("%d%d",&x,&y);printf("%d\n",cal(x-1,y-1));}return 0;
}


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



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

相关文章

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

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

HDU4737线段树

题目大意:给定一系列数,F(i,j)表示对从ai到aj连续求或运算,(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

圆与线段的交点

poj 3819  给出一条线段的两个端点,再给出n个圆,求出这条线段被所有圆覆盖的部分占了整条线段的百分比。 圆与线段的交点 : 向量AB 的参数方程  P = A + t * (B - A)      0<=t<=1 ; 将点带入圆的方程即可。  注意: 有交点 0 <= t <= 1 ; 此题求覆盖的部分。 则 若求得 t  满足 ; double ask(d

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja