[TIOJ 1332] 名義老爸

作法：

這題用到了 BST 和 Heap 之間的神秘關係， TIOJ 1193 也有用到類似的東西，作法在部落格裡也有。

這題要問的等於就是給你插入BST的順序，要建出這顆BST。假設現在這顆樹已經建完了，考慮把每個節點加上一個優先級，把第 i 個被插入的節點的優先級設為 i ，那麼會發現優先級會滿足最小堆性質，也就是加上優先級之後這顆BST變成了一顆Treap( 之後分別用 key 值和優先級代表每個節點的兩個數字 )。所以如果我們能建出這顆 Treap 就能建出原來的BST了。再注意到，其實 key 值從1到n代表的就只是對這顆 Treap 中序遍歷的順序，所以其實只要給定「按照中序遍歷的順序寫下節點的優先級，得到的數列( 之後把他叫 A )」，就可以決定一個 Treap 了，而這樣構造方法就會變得很簡單，在某個子樹 A[ l ... r ] 裡 優先級最小的數一定當根，設他是 A[ x ] 好了，那麼根的左子樹就是 A[ l ... x-1 ] ，右子樹就是 A[ x+1 ... r ]。( 這也被叫作笛卡爾樹 )。

但這樣乍看之下構造還是O(n^2)的，因為每次在作一個子樹的時候，都需要先找到哪個點要當根，如果直接作會花掉O(n)的時間，如果再開個線段樹作查詢的話複雜度也會有O(nlogn)，但實際上有O(n)構造笛卡爾樹的方法。

考慮 A[ 1 ... i ] 構成的笛卡爾樹，那麼可以知道從根走到 A[ i ] 的路徑一定是一直往右( 因為要保持中序遍歷是原數列 )，這時 A[ i+1 ] 要加進來，如果 A[ i+1 ] > A[ i ]，那直接插在 A[ i ]下面就好了，否則 A[ i ] 必須變成他的子孫，而且一定是左分支的子孫( 同樣的，因為要保持中序遍歷是原數列 )。所以一直沿著 A[ i ] 的祖先走上去，假設第一個遇到的優先值 < A[ i + 1 ]的節點叫 u ( 可能是空節點 0 ) ，上一個走過的節點叫 v ，那麼就把 A[ i + 1] 設成 u 的孩子 ( 右子樹 )， v 設成 A[ i + 1 ]的孩子(左子樹)，不難驗證這個構造方法就是我們要的笛卡爾樹。

但這樣看起來好像是O(n^2) ？ 因為每次沿著 A[ i ] 走上去的時候，也有可能衝到 O( n )次 ，但如果我們分析每個節點會被這樣走過幾次的話，會發現如果 u 在插入 A[ i + 1 ] 的時候被走過，那麼 u 就會被當作 A[ i + 1 ]的左子樹裡的點，這樣他之後就永遠不會再被走到了！所以這個算法的時間複雜度是O(n)。實作上我是用一個 stack 維護「從根走到 A[ i ]會經過哪些數」，可以明顯的看到每個數只會進出 stack 一次。

關於笛卡爾樹也可以看看這篇，裡面也有講到O(n)的構造方法。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
int a[maxn],inv[maxn] ;
int fa[maxn],ans[maxn] ;
stack<int> st ;
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) , inv[a[i]]=i ;
 
    fa[inv[1]]=0 ; st.push(inv[1]) ;
    for(int i=2;i<=n;i++)
    {
        if(inv[i]>st.top())
        {
            fa[inv[i]]=st.top() ;
            st.push(inv[i]) ;
            continue ;
        }
        int x ;
        while(!st.empty() && st.top()>inv[i])
            x=st.top() , st.pop() ;
        fa[inv[i]]= st.empty() ? 0 : st.top() ;
        fa[x]=inv[i] ;
        st.push(inv[i]) ;
    }
    for(int i=1;i<=n;i++) ans[a[i]]=a[fa[i]] ;
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]) ;
}