TIOJ::1603 . 胖胖殺蚯事件

http://tioj.infor.org/problems/1603

一題RMQ，因為不用更新，所以就拿來練習Sparse Table。



題目很簡單，給妳一堆查詢，問區間最大值減最小值。建兩張Sparse Table，Sparse Table是用DP的概念來解RMQ。

首先狀態 F(i，j) ，代表的是，從 i 到 i+2^j -1 之間的最大(小)值，因為有了二次方的概念所以複雜度降到了n log n。

初始值 F(i，0) 就代表 i 這格的值，之後轉移式就是 F(i，j) = max( F(i，j-1)，F( i + 2^j ，j-1 ) )。(一段區間的值等於他拆成一半之後左邊和右邊的值取最大(小)，有寫過線段樹就會很容易理解，這裡是用 botton-up 的概念，而線段樹是 top-down 的感覺，其中左邊區間就是 左界加上一半的長度，也就是DP中的 j-1(二的 j -1 次方)， 另外一半就是 i+j^2 開始，長度一樣是DP中的 j-1 ) 。

基本上FOR迴圈跑完就做完了，注意第一層迴圈是 J from 1 to log2(n)，然後才是 I ，因為當然要先把長度小的小塊做完，才能合併出長度大的大塊。

查詢的時候，取查詢的一半大一點的長度，也就是 log2(b-a+1)，注意要加一，不然 log2(0)會變負一會爆炸。為甚麼要取一半大一點呢，因為我們不一定有剛好的大小的塊，但是可以用兩塊合併起來，中間重疊一點點不影響答案(因為是最大最小值)。於是答案就是：

查詢 a b
k = log2(b-a+1)
max(F(a，k)，F(b-2^k+1，k))

這樣查詢就是兩塊剛好切齊左右界的重疊方塊。

時間複雜度  預處理 O(n log n)，查詢 O(1)
空間複雜度 O(n log n)

缺點是不能更新，空間大一點。功能不多學起來放著吧.......。

話說這題被 unsigned int 陰到了，2^31次方超過int囉!!!!

#include <cstdio>
#include <cmath>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define N 100001
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
unsigned int M[N][18],m[N][18],D[N];
int main(){
    int n,a,b,k,q;
    scanf("%d%d",&n,&q);
    F(n)scanf("%d",&D[i]),M[i][0]=m[i][0]=D[i];
    Fl(j,1,18)F(n)if(i+(1<<j)-1<n){
        M[i][j]=max(M[i][j-1],M[i+(1<<(j-1))][j-1]);
        m[i][j]=min(m[i][j-1],m[i+(1<<(j-1))][j-1]);
    }
    while(q--){
        scanf("%d%d",&a,&b);
        a--,b--;
        k=log2(b-a+1);
        printf("%d\n",max(M[a][k],M[b-(1<<k)+1][k])-min(m[a][k],m[b-(1<<k)+1][k]));
    }
}