186
poj 3264 Balanced Lineup【RMQ】
這道題是poj上麵RMQ最具代表性的一道題，沒有之一
題目也基本上就是一個裸RMQ的算法，看到這道題也可以用線段樹解決，決定還是要出一個線段樹的版本的，一道題搞懂兩個知識點，多好！
RMQ(Range Minimum/Maximum Query)問題：
RMQ問題是求給定區間中的最值問題。當然，最簡單的算法是O(n)的，但是對於查詢次數很多（設置多大100萬次），O(n)的算法效率不夠。可以用線段樹將算法優化到O（logn)（在線段樹中保存線段的最值）。不過，Sparse_Table算法才是最好的：它可以在O(nlogn)的預處理以後實現O(1)的查詢效率。下麵把Sparse Table算法分成預處理和查詢兩部分來說明(以求最小值為例)。
預處理:
預處理使用DP的思想，f(i, j)表示[i, i+2^j - 1]區間中的最小值，我們可以開辟一個數組專門來保存f(i, j)的值。
例如，f(0, 0)表示[0,0]之間的最小值,就是num[0], f(0, 2)表示[0, 3]之間的最小值, f(2, 4)表示[2, 17]之間的最小值
注意, 因為f(i, j)可以由f(i, j - 1)和f(i+2^(j-1), j-1)導出, 而遞推的初值(所有的f(i, 0) = i)都是已知的
所以我們可以采用自底向上的算法遞推地給出所有符合條件的f(i, j)的值。
查詢:
假設要查詢從m到n這一段的最小值, 那麼我們先求出一個最大的k, 使得k滿足2^k <(n - m + 1).
於是我們就可以把[m, n]分成兩個(部分重疊的)長度為2^k的區間: [m, m+2^k-1], [n-2^k+1, n];
而我們之前已經求出了f(m, k)為[m, m+2^k-1]的最小值, f(n-2^k+1, k)為[n-2^k+1, n]的最小值
我們隻要返回其中更小的那個, 就是我們想要的答案, 這個算法的時間複雜度是O(1)的.
例如, rmq(0, 11) = min(f(0, 3), f(4, 3))
也就是出現了重疊，區間劃分為[0,7]和[4,11]
由此我們要注意的是預處理f(i,j)中的j值隻需要計算log(n+1)/log(2)即可，而i值我們也隻需要計算到n-2^k+1即可。
AC的代碼：
#include <stdio.h>
#include <cmath>
#define MAXN 50002
int cow[MAXN];
//放區間最大值和最小值的數組，後麵的16代表2^16=65536
int maxl[MAXN][16], minl[MAXN][16];
inline int max(int a,int b){ return a>b?a:b; }
inline int min(int a,int b){ return a<b?a:b; }
//預處理函數
void preprocess(int N)
{
//dp
//因為2^t要覆蓋l-r+1，所以t=ln(r-l+1)/ln(2)，因為N是6，所以這裏t為4
int t=int(log((double)N)/log(2.0));
for(int j=1;j<=t;j++)
{
for(int i=1;i+(1<<(j-1))-1<N;i++)
{
maxl[i][j]=max(maxl[i][j-1],maxl[i+(1<<(j-1))][j-1]);
minl[i][j]=min(minl[i][j-1],minl[i+(1<<(j-1))][j-1]);
}
}
}
//查詢函數
void work(int l,int r,int N)
{
//因為2^t要覆蓋l-r+1，所以t=ln(r-l+1)/ln(2)
int k=int(log((double)(r-l+1))/log(2.0));
int maxans=max(maxl[l][k],maxl[r-(1<<k)+1][k]);
int minans=min(minl[l][k],minl[r-(1<<k)+1][k]);
printf("%d\n",maxans-minans);
}
int main()
{
int N,Q;
int i;
scanf("%d%d",&N,&Q);
for(i=1;i<=N;i++)
{
scanf("%d",&cow[i]);
maxl[i][0]=minl[i][0]=cow[i]; //init
}
preprocess(N);
int x,y;
while(Q--)
{
scanf("%d%d",&x,&y);
work(x,y,N);
}
return 0;
}
下麵粘貼一個寫的很不錯，通俗易懂的代碼：
#include<cstdio>
#include<iostream>
using namespace std;
#define MAXN 50010
int n,q;
int p[MAXN];
int dpmin[MAXN][20],dpmax[MAXN][20],pw[20];
int log(int n)
{
int cnt=0;
while(n)
{
cnt++;
n>>=1;
}
return cnt-1;
}
int main()
{
pw[0]=1;
for(int i=1;i<=20;i++)
pw[i]=2*pw[i-1];
while(2==scanf("%d%d",&n,&q))
{
for(int i=0;i<n;i++)
scanf("%d",p+i);
for(int i=0;i<n;i++)
{
dpmin[i][0]=p[i];
dpmax[i][0]=p[i];
}
for(int j=1;j<=log(n);j++)
for(int i=0;i<n;i++)
{
if(i+pw[j-1]>=n)
continue;
dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+pw[j-1]][j-1]);
dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+pw[j-1]][j-1]);
}
for(int i=0;i<q;i++)
{
int a,b;
scanf("%d%d",&a,&b);
a--,b--;
int j=log(b-a+1);
int ansmax,ansmin;
ansmax=max(dpmax[a][j],dpmax[b-pw[j]+1][j]);
ansmin=min(dpmin[a][j],dpmin[b-pw[j]+1][j]);
printf("%d\n",ansmax-ansmin);
}
}
return 0;
}
最後更新：2017-04-03 05:39:36