IE8

由於新滑鼠的很多功能鍵都只適用於"純"IE瀏覽器，所以莫名其妙灌了IE8，用用看，啾靜好不好用呢?

目前還沒有答案

實在很久沒主動打開"純"IE了

Tree Reconstruction

問題：只知道一顆樹的 preorder 和 inorder ，要求出樹的架構。
這是個能用 D&C 解決的好問題。在 inorder 之中， root 兩邊分別為左子樹和右子樹；而 preoder 的最左邊的元素就是 root ──故可以利用 root 來分出左子樹和右子樹。每個子樹又是一棵樹，又可以再分割，如此便可求出整棵樹的架構。
能知道分割的關鍵在哪裡，應該就不難理解了。會有唯一解。
至於只有 preorder 和 postorder 的話，是做不出答案的。正是因為這兩個 order 當中，找不到可以分割的地點。
那麼 levelorder 呢？大家就自己想想吧。（ order 的部分可以寫成一篇長長的文章吧。我孤陋寡聞，實在不想多寫。）

這裡也是列出幾題，相信很多人都有看過。

UVa 10701 536 548 10410

Range Minimum(Maximum) Query, RMQ

從這位強者的網誌轉錄:
http://gozule.blogspot.com/2009/02/range-minimummaximum-query-rmq.html

Input：array A[0, N]
Output： the index of minimum(maximum) value between two given indices.
RMQ的功能是若有一群資料放在array中，在經過preprocessing後，可在O(1)的時間內找出index i~j之間的最小(大)的元素。目前preprocessing最快是O(n)，也就是只需要O(n)的時間就可以處理完成。

以下介紹O(nlog(n))的preprocessing方法，O(n)的方法是由此法去改進，所以先了解此法相當重要且因程式碼容易撰寫，所以也相當適合在ACM中使用。

假設array的長度2的n次方。
建立一個大小為n x log(n)的矩陣M，用來存放RMQ的結果，其中M[i][j]是指以index i開頭，長度為2^j次方內最小元素的index。
使用dynamic programming方法建立M，需O(nlogn) time。

//time complexity: O(nlogn)
void preprocess(int M[MAXN][LOGMAXN], int A[MAXN], int N)
{
int i, j;

//initialize M for the intervals with length 1
for (i = 0; i < N; i++)
M[i][0] = i;
//compute values from smaller to bigger intervals
for (j = 1; 1 << j <= N; j++)
for (i = 0; i + (1 << j) - 1 < N; i++)
if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
M[i][j] = M[i][j - 1];
else
M[i][j] = M[i + (1 << (j - 1))][j - 1];
}

//output: the index of the minimum value between index i and j
int RMQ(int i, int j, int M[MAXN][LOGMAXN], int A[MAXN], int N)
{
if(i<0 || i>=N || j<0 || j>=N)
return -1;

if(i > j) //swap i, j
i ^= j, j ^= i, i ^= j;

int k = (int)(log(j-i)/log(2.0)),
rem = j-(1< return (A[M[i][k]] > A[M[rem][k]] ? M[rem][k] : M[i][k]);
}