\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年8月31日 星期一

[ Lowest Common Ancestor , LCA Euler Tour Technique ] 最近共同祖先樹壓平轉RMQ算法

想法就是把樹壓平,然後紀錄當前節點u的深度在dep[u],紀錄時間戳記,進入的時候要紀錄一次,出來的時候也要記錄,把當前點u進入的時間戳紀錄在in[u]中,時間戳的大小為2*n,所以必須用兩倍的記憶體來維護。之後就轉成RMQ問題
查詢a,b兩點的LCA=dep[in[a]]到dep[in[b]]中,最小深度的時間戳經過的那個點
查詢:
RMQ的部分就要自己維護了,使用線段樹效能會非常差,在n,q<=100000的情況下使用稀疏表的效能與使用樹鏈剖分的效能差不多

[ Lowest Common Ancestor , LCA Doubling Search ] 最近共同祖先倍增演算法

首先建立一張倍增表,pa[i][x]表示x的第\(2^i\)的祖先,若不存在則為\(-1\),可以在DFS或BFS的過程中求得,複雜度為\(\ord{N*MAX\_LOG}\)

對於每筆詢問,我們可以利用剛剛求得的倍增表,在\(\ord{MAX\_LOG}\)的時間在線查詢
先將要查詢的a,b兩點較深的點移至較淺的點的深度,之後二分搜LCA的位置
附上模板:

[ Lowest Common Ancestor , LCA Tarjan's Algorithm ] 最近共同祖先tarjan演算法

tarjan算法的步驟是(當dfs到節點u時):

在並查集中建立僅有u的集合,設置該集合的祖先為u
對u的每個孩子v:
  1. 遞迴處理v
  2. 合併v的集合到父節點u的集合,確保集合的祖先是u
設置u為已遍歷
處理關於u的查詢,若查詢(u,x)中的x已遍歷過,則LCA(u,x) = x所在的集合的祖先

因為只進行過一次DFS,所以複雜度為\(\ord{(N+Q)*\alpha(N)}\),為了優化並查集,這裡採用啟發式合併,因此為了記錄集合的祖先而外增加了一個數組head
其雖為線性,但是效率並不怎麼好,跟倍增法的效能差不多
使用方法也很簡單,只需要將每個詢問的兩點記錄起來即可

2015年8月5日 星期三

[ Mo's algorithm ]莫隊算法

對於一些詢問區間答案的資料結構題,我們已經知道了區間[l,r]的答案,且能在極少的時間( \(\ord 1 \) or \(\ord{logN}\) )內得到區間[l+1,r]、[l-1,r]、[l,r+1]、[l,r-1]的答案,題目也准許離線,只要滿足這些性質就可以使用莫隊。

首先我們須將所有詢問記錄下來,將序列分成sqrt(n)塊,找出每筆詢問l所在的塊,每塊內r由小排到大

這裡n是序列的長度

之後就按造順序一個一個將序列元素在一些維護費用很小的資料結構進行插入刪除,直到等於當前區間為止,此時就可以把這個資料結構的答案存到ans陣列裡,然後結束後一次輸出

這裡進行一下簡單的證明:
  • 假設序列長度為N,我們將序列每K個分成一塊,在排完序後,左界屬於同一塊的詢問,每次都不會移動操過K次;而左界屬於不同塊的操作,從第i塊移動到第i+1塊最多要移動2*K次,總共分成N/K塊,故移動次數加起來不操過2*K*(N/K)=2*N次,因此左界移動的複雜度為\(\ord{Q*K}+\ord N\),Q為詢問次數
  • 對於右界,在同一塊內因為是遞增的關係所以移動次數不會操過N次,而最多只有N/K塊,因此複雜度為\(\ord{N*N/K}\)
  • 這個時候我們可以取K=sqrt(N)得到一個複雜度為\(\ord{Q*K+N+N*N/K}=\ord{(Q+N)*sqrt(N)}\)的方法
這是區間眾數的模板(對於每個詢問l,r輸出區間[l,r]眾數的個數):