題目鏈接：[點擊打開鏈接](http://poj.org/problem?id=1436) 題意：n條豎直線段，如果兩條線段之間可見（即可以用一條水平線段連接而不觸碰其他線段），則稱它們可見。 如果三條線段任意兩條都可見， 則稱它們為a triangle of segments， 求a triangle of segments的個數 思路： 一開始真沒想到n^3的復雜度可以過。。。 ?如果這樣的話， 問題的關鍵就是怎樣判斷任意兩個線段是否可見。 那么如果對y坐標建立區間， 這就成了線段樹的區間覆蓋問題。 另外， 由于是用點代替線段， 所以對于”可見“這個問題， 就會出現問題， 比如 ?有三條線段[1,4]、[1,2]、[3,4]， 則在[1,4]區間中可以看見3條線段， 即可以通過[2,3]的空隙看見第一條線段。 ? 解決方法很簡單， 把坐標擴大2倍就行了，這樣[1,2]變成[2,4]，[3,4]變成[6,8]，空出了一個5。 細節參見代碼： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int mod = 1000000000 + 7; const int INF = 1000000000; const int maxn = 8000 + 10; int T,n,t,q,l,r,c,col[maxn<<3],y[maxn<<1]; bool vis[maxn][maxn]; struct node { int ly, ry, x; node(int l=0, int r=0, int xx=0):ly(l),ry(r),x(xx) {} bool operator < (const node& rhs) const { return x < rhs.x || (x == rhs.x && ly < rhs.ly); } }a[maxn]; void pushdown(int o) { if(col[o] >= 0) { col[o<<1] = col[o<<1|1] = col[o]; col[o] = -1; } } void update(int L, int R, int c, int l, int r, int o) { int m = (l + r) >> 1; if(L <= l && r <= R) { col[o] = c; return ; } pushdown(o); if(L <= m) update(L, R, c, l, m, o<<1); if(m < R) update(L, R, c, m+1, r, o<<1|1); } void query(int L, int R, int id, int l, int r, int o) { int m = (l + r) >> 1; if(col[o] >= 0) { vis[id][col[o]] = true; return ; } if(l == r) return ; if(L <= m) query(L, R, id, l, m, o<<1); if(m < R) query(L, R, id, m+1, r, o<<1|1); } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); int m = 0; for(int i=0;i<n;i++) { scanf("%d%d%d",&a[i].ly, &a[i].ry, &a[i].x); m = max(m, max(a[i].ly, a[i].ry)); } sort(a, a+n); memset(col, -1, sizeof(col)); memset(vis, false, sizeof(vis)); for(int i=0;i<n;i++) { int l = a[i].ly; int r = a[i].ry; query(2*l, 2*r, i, 0, 2*m, 1); update(2*l, 2*r, i, 0, 2*m, 1); } int ans = 0; for(int i=n-1;i>=0;i--) { for(int j=i-1;j>=0;j--) { if(vis[i][j]) { for(int k=j-1;k>=0;k--) { if(vis[i][k] && vis[j][k]) ++ans; } } } } printf("%d\n",ans); } return 0; } ~~~