POJ3264：Balanced Lineup——题解+st表解释

我早期在csdn的博客之一，正好复习st表就拿过来。
http://write.blog.csdn.net/mdeditor#!postId=63713810

这道题其实本身不难（前提是你得掌握线段树或者st表当中的一种）
那么这道题我们来讲一讲st表（因为这题询问次数有点多）
一般关系式
dp[i][j]=min/max(dp[dp[i][j-1],dp[i+pow(2,j-1)][j-1]])
可以看出来吧，其实这就是动态规划
好的我们来解释一下关系式是什么吧
首先这个是一个二分，具体是什么呢：
其中的i代表起点，2^j代表起点到中点的长度。
如果还不懂的话，我们来看一下样例（求最小值）
2   6   4   8   9   7   11
好的，我们来模拟一下程序的运作
dp[1][0]=2;dp[2][0]=6……dp[7][0]=11;
然后dp[1][1]=min(2,6)=2; dp[3][1]=min(4,8)=4;……dp[6][1]=min(7,11)=7;
再然后dp[1][2]=min(2,4)=2;……
如此这般如此这般
怎么样，给一个样例是不是就很清楚了。
然后就是查询了，但是有时候因为查询区间比较大，没办法一步到位怎么办
例如查询1-5的区间，然而按照我们上面的定义来的话，我们最大可以调用dp[1][2]，然而却落了第五个点。
其实很简单，结果=min(dp[1][2],dp[2][2])
原因也无需解释了吧
那么我们用代码实现吧，顺便把这道题写了吧

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int maxn[50001][30],minn[50001][30];
int qpow(int a){
    return (1<<a);
}
void st(int n){
    for(int j=1;j<=int(log2(n));j++){
        for(int i=1;i<=n;i++){
            int p=i+pow(2,j)-1;
            if(p>n)continue;
            maxn[i][j]=max(maxn[i][j-1],maxn[i+int(qpow(j-1))][j-1]);
            minn[i][j]=min(minn[i][j-1],minn[i+int(qpow(j-1))][j-1]);
        }
    }
    return;
}
int main(){
    int n,q,k,x,y;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&maxn[i][0]);
        minn[i][0]=maxn[i][0];
    }
    st(n);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&x,&y);
        if(y<x){
            int t=x;x=y;y=t;
        }
        double s=y-x+1;
        int ke=log2(s);
        int he=qpow(int(log2(s)));
        int t1=max(maxn[x][int(log2(s))],maxn[y-he+1][ke]);
        int t2=min(minn[x][int(log2(s))],minn[y-he+1][ke]);
        printf("%d
",t1-t2);
    }
    return 0;
}