IOI 2004 Empodia

首先, for each i, 搵出由 i 開始且最短的 framed interval, 記完結位置為 p[i] (即 i..p[i] 為一 framed interval), 搵最短是因為一些更長的可以肯定不是 empodia


對每個 i, 可以在 O(N) 搵到
由於 framed interval 的特性, e[i..j] 滿足以下條件即為 framed interval

• e[i] < e[j]
  
• e[i] = min{e[k], i < k < j}
  
• e[j] = max{e[k], i < k < j}
  

很容易可以做到

之後就係delete一些不是 empodia 的 framed interval
方法就係 for each i, 睇下有冇 j>i 而且 p[j]<p[i]

總時間O(N²)


順帶一提, 解題報告話呢題有O(N)方法, 不過是論文來的.. (只有一個test case需要O(N), 佢應該唔預有人諗到..)