PKU2352-Stars

題目：http://poj.org/problem?id=2352
滿天星斗的天空有N(不超過15000)顆星星，給出它們的座標(非負整數)
(已經幫你按照Y座標排序，如果Y相同會照X排序)
請問0,1,...,N-2,N-1級星分別有幾顆呢？(N=5即輸出0,1,2,3,4級星的數目)
我們定義一顆星星的等級是L，表示有L顆其他星星在這顆星的左下方(正左和正下都算)

(2011.12.16補上解題報告)

程式碼：http://codepad.org/b1M5cYRz
經典線段樹/樹狀數組問題
這裡直接用樹狀數組來作

題目已經非常仁慈的幫我們把排序都省了
所以現在這些星星的資料順序，已經可以保證如果順序i>j，那麼i不可能在j更高的地方
(換句話說如果i>j, 一定有y[i]>=y[j])
既然Y座標已經考慮好了，那麼就依次將它們插入樹狀數組裡，
並且每次都統計對當前的X座標xi，[0...xi]有幾顆星星(就是該星的級數)
圓滿AC

順帶一提，X座標和Y座標也很仁慈的給不超過32000...所以X座標不必離散化

總結這真是一道非常仁慈的好題目