主題
題目連結(jié)：
題目大意：
輸入第一列給定兩正整數(shù) n 、 q（n 、 q ≦ 5 × 10 ^ 6），代表現(xiàn)在有 n 個(gè)人依序站在位置 1 ～ n 上，並且有 q 筆的操作。
接著的 q 列輸入，每列先給定一個(gè) '?' 或是 '-'，並跟隨一個(gè)正整數(shù) x（1 ≦ x ≦ n）。前者（'?'）代表我們要詢問(wèn)位置 x 上往右（即往 x 、 x + 1 、 x + 2 等等的方向看去，注意記得 x 本身是有被包含的）第一個(gè)還存在的人之位置為何，如果右側(cè)沒(méi)有人就輸出 -1；而後者（'-'）則代表我們要把位置 x 的人移出隊(duì)伍之中。
請(qǐng)輸出每次 '?' 之詢問(wèn)的結(jié)果。
（原作者注：「由於生測(cè)資的時(shí)候出現(xiàn)意外，每筆測(cè)資除了第一行以外每一行最後面都有一個(gè)空格。」）
時(shí)限：0.6s
測(cè)資量：> 50MB
範(fàn)例輸入：
5 10
? 1
- 3
? 3
- 2
? 1
? 2
- 4
? 3
- 5
? 3
範(fàn)例輸出：
1
4
1
4
5
-1
解題思維：
這題可以用併查集（Union-Find Set）解，不過(guò)不是一般常見(jiàn)的型態(tài)。因此下面就先介紹一下併查集這個(gè)資料結(jié)構(gòu)。
任何資料結(jié)構(gòu)只要滿足以下操作就可以叫做「併查集」：
建立（Make-set）：顧名思義，建立一個(gè)新的集合，該集合包含一個(gè)作為參數(shù)傳入的元素 x。由於以下兩個(gè)操作的重要性較大，因此此操作通常會(huì)被某些人忽略不算在「必需」之內(nèi)。
查詢（Find）：查找一元素目前位於哪個(gè)集合之中。通常一個(gè)集合會(huì)有一個(gè)代表（Representative），可以用來(lái)判斷兩集合是否相同。
合併（Union）：將兩個(gè)集合合而為一。
因?yàn)橛泻蟻阋约安樵儍蓚€(gè)操作，因故而稱為併查集（Union-Find set）。
而併查集常見(jiàn)的有兩種表示法，一種為連結(jié)串列（Linked List）、另一種為森林（Forest）。因?yàn)榻^大部分的時(shí)候只會(huì)用到森林，因此以下只介紹森林的表示法：
下圖為一個(gè)有著兩棵樹(shù)的例子。
其中每棵樹(shù)代表一個(gè)集合，且 e 和 f 為各自的樹(shù)之根節(jié)點(diǎn)（root）以及「代表」。
可以看到在這樣的表示法之下，每個(gè)操作的時(shí)間複雜度為：
Make-Set(x)：O(1)，因?yàn)橹皇且⒁粋€(gè)新的節(jié)點(diǎn)而已。
Find(x)：O(h)，其中 h 為 x 所在的樹(shù)之高度，因?yàn)槲覀円獜?x 循著邊跑到 root。
Union(x, y)：O(h)，因?yàn)橐日业?x 的根節(jié)點(diǎn)以及 y 的根節(jié)點(diǎn)，再將 x 的指向 y 的（反過(guò)來(lái)指也可以）。
而我們有兩種啟發(fā)式（Heuristic）可以最佳化上述操作時(shí)間複雜度的方式：
第一種為按秩合併（Union-by-rank），其代表的意思為在合併兩棵樹(shù)的時(shí)候把比較矮的（或是節(jié)點(diǎn)數(shù)少的）根節(jié)點(diǎn)指向比較高的（或是節(jié)點(diǎn)數(shù)多的）根節(jié)點(diǎn)。
因?yàn)榘臉?shù)中的節(jié)點(diǎn)被詢問(wèn)「代表」的比例比起高的樹(shù)中的節(jié)點(diǎn)還要來(lái)得低。因此在大部分情形下（或是以平均來(lái)看），高的樹(shù)節(jié)點(diǎn)多走了一層會(huì)比矮的樹(shù)節(jié)點(diǎn)多走一層還要虧。以上面的圖為例，把兩棵樹(shù)合併的話會(huì)是這樣：
第二種為路徑壓縮（Path Compression），即當(dāng)每次呼叫為 Find(x) 找到 x 所在的樹(shù)之根節(jié)點(diǎn) r 後，把 x 改成直接指向 r。承上例，當(dāng)我們呼叫完 Find(c) 後，我們會(huì)得到：
呼叫為 Find(d) 後，我們會(huì)得到：
如果我們把上述兩種策略一起使用的話則就會(huì)變成一般我們常見(jiàn)到的併查集（Union-Find Set）之形式，其中均攤下（Amortized）單次 Find 和 Union 的操作之時(shí)間複雜度變?yōu)?α(n)，其中 n 為全部元素的總數(shù)、α(n) 為反阿克曼函數(shù)（Inverse Ackermann Function），其函數(shù)值成長(zhǎng)速度極慢（例如若 n = 2 ^ 2 ^ 2 …… ^ 2 之 k 層的指數(shù)塔，則 α(n) = k）。
有興趣探究為何是這樣的時(shí)間複雜度且英文程度尚可的讀者，可以考慮參見(jiàn)演算法的經(jīng)典教科書(shū)——Introduction to Algorithms, Third Edition（或以四位作者的名字之開(kāi)頭字母稱為 CLRS）裡的第 21 章。
實(shí)際上遇到需要併查集的問(wèn)題時(shí)，實(shí)作森林的方式基本上不是真的用好幾個(gè)樹(shù)節(jié)點(diǎn)來(lái)表示，而是直接把所有東西攤平成若干個(gè)陣列來(lái)儲(chǔ)存。例如現(xiàn)在每個(gè)元素剛好是編號(hào) 1 ～ n，那麼我們就直接利用一個(gè)陣列 parents 來(lái)代表每個(gè)元素所指向的元素；而秩（rank）可以用另一個(gè)陣列來(lái)表示。
回到本題原先的目標(biāo)——我們要找到從每個(gè)位置 x 開(kāi)始往右第一個(gè)遇到有人在的位置（如果都沒(méi)有人，則為 -1）。正如一開(kāi)始預(yù)告的，本題可以使用並查集解出。那麼要怎麼做呢？一樣，我們一開(kāi)始有一個(gè)長(zhǎng)度為 n + 2 的陣列 parents，其中 parents[i] 代表從位置 i 開(kāi)始往右第一個(gè)有人的位置。
一開(kāi)始對(duì)於所有 i = 1 ～ n 之值 parents[i] = i，因?yàn)槊總€(gè)位置都有站一個(gè)人。然後為了實(shí)作方便 parents[n + 1] = -1，代表再往右就沒(méi)有人了。因此，我們可以看到每個(gè)位置 x 所在的集合之「代表」，即為從 x 開(kāi)始往右第一個(gè)有人的位置。
現(xiàn)在定義一個(gè)函式 Find(x)，其可以找到 x 所在集合之「代表」。由於現(xiàn)在我們還沒(méi)套用任何最佳化的策略，所以我們的 Find 函式只有
while (parents[x] != x && parents[x] != -1)
++x;
return parents[x]；
之內(nèi)容，也就是相當(dāng)暴力地去往右找第一個(gè)有人的位置。
那麼現(xiàn)在我們便可以把題目定義的兩種指令，'?' 以及 '-' 給實(shí)作出來(lái)。
因?yàn)?'?' 就是詢問(wèn)本身，所以我們輸出 Find(x) 即可；而 '-' 是要移除位置 x 上的人，因此我們可以視為位置 x 所在的集合與位置 x + 1 所在的集合合併，因此 parents[x] = Find(x + 1)，可以看到我們把原先併查集的 Union 操作藏在了這裡。
接著我們?cè)囍子每纯聪惹疤岬降膬煞N啟發(fā)式的最佳化策略，即按秩合併以及路徑壓縮。
首先可以看到我們所有位置 x 的「箭頭」都是指向右邊（也就是 x + 1 之方向）。而按秩合併是看兩者集合之高度或大小來(lái)決定合併方向，因此有可能會(huì)使箭頭往左指，而這不是我們樂(lè)見(jiàn)的結(jié)果。因此無(wú)法套用按秩合併。
接著是路徑壓縮，而這個(gè)策略是可以套用的。因此現(xiàn)在我們的 Find 函式會(huì)變得像是如下的結(jié)果：
第一部分是在找出「代表」，如下：
int index = x;
while (parents[index] != x && parents[index] != -1)
index = parents[index];
int result = parents[index];
第二部分是把路上經(jīng)過(guò)所有位置的「代表」變成我們剛剛找到的「代表」，而這個(gè)行為即是路徑壓縮（Path Compression）：
int buffer = x;
while (buffer < index) {
int temporary = parents[buffer];
parents[buffer] = result;
buffer = temporary;
}
return result;
而這樣便完成了我們的併查集最佳化。
那麼總體時(shí)間複雜度呢？可以看到我們有 n 個(gè)位置，所以有 n 個(gè) O(1) 時(shí)間的 Make-Set 以及至多 n - 1 次的 Union，並假設(shè)我們總共呼叫 Find() 函式 f 次。由於我們的併查集只有使用路徑壓縮的策略，因此跟經(jīng)常使用到的併查集不一樣，我們的時(shí)間（根據(jù) CLRS）會(huì)是
也就是當(dāng) f 之值越大時(shí)，單次 Find() 平均所花的時(shí)間越少。
但是很不幸的是本題到這裡並還沒(méi)有結(jié)束，可以看到本題的測(cè)資量異常地大且時(shí)限非常地緊。所以我們需要使用如這題中所使用的輸出入最佳化以及編譯器最佳化等等之手段。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
