这道题做了快两天了。首先就是按照这些竖直线段的横坐标进行从左到右排序。
将线段的端点投影到y轴上，线段树所维护的信息就是y轴区间内被哪条线段所覆盖。
对于一条线段来说，先查询和它能相连的所有线段，并加入到一个有向图里面，一遍后面O(n3)暴力统计答案。
然后就是update，用这个线段将对应的区间“染色”
还要注意一个情况就是：
0 3 1， 0 1 2， 2 3 2， 0 3 3折四条线段
| | |
| |
| | |
很明显第一和第三条线段是可相连的，但是中间两条会覆盖掉左边的线段，根据以往的经验，之间将所有纵坐标乘二就好啦。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 8000 + 10; 7 int setv[maxn << 2]; 8 bool G[maxn][maxn]; 9 10 int n, qL, qR, v; 11 12 struct Segment 13 { 14 int y1, y2, x; 15 Segment() {} 16 Segment(int y1, int y2, int x):y1(y1), y2(y2), x(x) {} 17 bool operator < (const Segment& rhs) const 18 { return x < rhs.x; } 19 }seg[maxn]; 20 21 void pushdowm(int o) 22 { 23 if(setv[o]) 24 { 25 setv[o*2] = setv[o*2+1] = setv[o]; 26 setv[o] = 0; 27 } 28 } 29 30 void update(int o, int L, int R) 31 { 32 if(qL <= L && qR >= R) { setv[o] = v; return; } 33 pushdowm(o); 34 int M = (L + R) / 2; 35 if(qL <= M) update(o*2, L, M); 36 if(qR > M) update(o*2+1, M+1, R); 37 } 38 39 void query(int o, int L, int R) 40 { 41 if(setv[o]) { G[v][setv[o]] = true; return; } 42 if(L == R) return; 43 int M = (L + R) / 2; 44 if(qL <= M) query(o*2, L, M); 45 if(qR > M) query(o*2+1, M+1, R); 46 } 47 48 int main() 49 { 50 //freopen("in.txt", "r", stdin); 51 52 int T; scanf("%d", &T); 53 while(T--) 54 { 55 memset(setv, 0, sizeof(setv)); 56 memset(G, false, sizeof(G)); 57 58 scanf("%d", &n); 59 for(int i = 1; i <= n; i++) scanf("%d%d%d", &seg[i].y1, &seg[i].y2, &seg[i].x); 60 sort(seg + 1, seg + 1 + n); 61 for(int i = 1; i <= n; i++) 62 { 63 qL = seg[i].y1 * 2; qR = seg[i].y2 * 2; 64 v = i; 65 query(1, 0, maxn * 2); 66 update(1, 0, maxn * 2); 67 } 68 69 int ans = 0; 70 for(int i = 1; i <= n; i++) 71 for(int j = 1; j <= n; j++) if(G[i][j]) 72 for(int k = 1; k <= n; k++) if(G[i][k] && G[j][k]) ans++; 73 printf("%d ", ans); 74 } 75 76 return 0; 77 }