Balanced Lineup POJ - 3264（RMQ）

2024-01-02 12:18

文章标签 poj rmq balanced 3264 lineup

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

Balanced Lineup POJ - 3264

题目连接

题意：给出一个数列，Q个询问，问区间[A, B]中最大值与最小值的差；
思路：线段树可以做，维护最大最小值，直接查找就可以；但是现在要用RMQ做；
何为RMQ？(Range Minimum/Maximum Query) 区间最值询问，通过O(nlogn)的预处理可以在O(1)的时间内找到区间的最值；下面以最大值为例：
令Fmax[i][j]表示区间[i, i+2^j]中的最大值；那么F[i][j]=max(F[i][j-1], F[i+2^(j-1)][j-1]);

init(){for(int j=1; (1<<j)<=n; j++){for(int i=1; i+(1<<j)-1<=n; i++){Fmax[i][j]=max(Fmax[i][j-1], Fmax[i+(1<<(j-1))][j-1]);}}
}

对于区间[A, B]内的询问有：

int k=(int)(log(B-A+1.0)/log(2.0));
query(A, B)=max(Fmax[A][k], Fmax[B-(1<<k)+1][k]);

本题代码：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
const int maxn=5e4+10;
int Fmax[maxn][20], Fmin[maxn][20], n, Q;
void init(){for(int i=1; (1<<i)<=n; i++){for(int j=1; j+(1<<i)-1<=n; j++){Fmax[j][i]=max(Fmax[j][i-1], Fmax[j+(1<<(i-1))][i-1]);Fmin[j][i]=min(Fmin[j][i-1], Fmin[j+(1<<(i-1))][i-1]);}}
}
int main(){while(~scanf("%d%d", &n, &Q)){for(int i=1; i<=n; i++){scanf("%d", &Fmax[i][0]);Fmin[i][0]=Fmax[i][0];}init();while(Q--){int x, y;scanf("%d%d", &x, &y);int k=(int)(log(y-x+1.0)/log(2.0));printf("%d\n", max(Fmax[x][k], Fmax[y-(1<<k)+1][k])-min(Fmin[x][k], Fmin[y-(1<<k)+1][k]));}}   return 0;
}