POJ 1436 Horizontally Visible Segments（線段樹建圖+枚舉）

題目連接配接：

題意：給一些線段，每個線段有三個值y1, y2, x代表起點為（x, y1），終點為（x, y2）的線段。當從一個線段可以作水準線到另一個線段并且不穿過其他線段時，就稱這兩個線段時水準可見的。當三個線段可以兩兩水準可見，就稱為形成一個線段三角。問：在這些線段中有多少個這樣的線段三角？

分析：可以把每條線段看做是一個點，如果它和其他線段是水準可見的，就将這兩個點相連，由于是無向圖，就是你能看到我，我也能看到你，是以需要連接配接兩次（map[a][b] = 1; map[b][a] = 1;）。然後問題就是如何生成存放線段關系的圖，可以用線段樹來求。假如現在周遊到第i條線段，那麼第i條線段所能看到的是前面區間最新的線段，如圖：

線段5隻能看到1、2、4，不能看到3，是以可以用線段樹區間修改的方法來生成這個樹。

初始化set數組（存放線段的标号）全為-1，當周遊到某條線段時，對線段的那段區間進行查詢，如果查詢到的區間有值，說明可以看到線段set[o]，然後即相連，如果查詢到的區間一直是-1，就一直深搜，直到到達葉子節點傳回。查詢結束之後将目前線段插入到線段樹中，即把區間更新。因為都是整數，是以某兩條線段可見可能是在0.5的時候可見，是以需要預處理一下線段的區間，将區間擴大至2倍即可。

建完圖之後暴力枚舉每三個點即可。

代碼如下：