區間合并 --- Codeforces 558D : Gess Your Way Out ! II D. Guess Your Way Out! II Problem's Link: http://codeforces.com/problemset/problem/558/D

Mean: 

一棵滿二叉樹，樹中某個葉子節點是出口，目的是尋找這個出口。再給定Q個詢問的結果，每個結果告訴我們在第i層中(l,r)覆寫的葉結點是否包含出口。

analyse:

基本思路：多個區間求交集。

具體實作：

對于每一個詢問，把它轉化到最底層。并且把不在(l,r)區間的詢問改為在(最左邊，l-1)和(r+1,最右邊)的形式，這樣一來全部都變成了在(l,r)區間的描述。

區間統計：

對左右區間起點和終點組成的集合進行排序。然後找到答案存在的區間，如果區間長度=1，答案唯一；長度>1，答案不唯一;長度=0，無解。

Trick:會爆int。

Time complexity: O(n)

Source code: