轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年12月15日 星期一

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]));
    }
}