这道题做了快两天了。首先就是按照这些竖直线段的横坐标进行从左到右排序。
将线段的端点投影到y轴上，线段树所维护的信息就是y轴区间内被哪条线段所覆盖。
对于一条线段来说，先查询和它能相连的所有线段，并加入到一个有向图里面，一遍后面O(n3)暴力统计答案。
然后就是update，用这个线段将对应的区间“染色”
还要注意一个情况就是：
0 3 1， 0 1 2， 2 3 2， 0 3 3折四条线段
| | |
| |
| | |
很明显第一和第三条线段是可相连的，但是中间两条会覆盖掉左边的线段，根据以往的经验，之间将所有纵坐标乘二就好啦。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
int setv[maxn << ];
bool G[maxn][maxn]; int n, qL, qR, v; struct Segment
{
int y1, y2, x;
Segment() {}
Segment(int y1, int y2, int x):y1(y1), y2(y2), x(x) {}
bool operator < (const Segment& rhs) const
{ return x < rhs.x; }
}seg[maxn]; void pushdowm(int o)
{
if(setv[o])
{
setv[o*] = setv[o*+] = setv[o];
setv[o] = ;
}
} void update(int o, int L, int R)
{
if(qL <= L && qR >= R) { setv[o] = v; return; }
pushdowm(o);
int M = (L + R) / ;
if(qL <= M) update(o*, L, M);
if(qR > M) update(o*+, M+, R);
} void query(int o, int L, int R)
{
if(setv[o]) { G[v][setv[o]] = true; return; }
if(L == R) return;
int M = (L + R) / ;
if(qL <= M) query(o*, L, M);
if(qR > M) query(o*+, M+, R);
} int main()
{
//freopen("in.txt", "r", stdin); int T; scanf("%d", &T);
while(T--)
{
memset(setv, , sizeof(setv));
memset(G, false, sizeof(G)); scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d%d%d", &seg[i].y1, &seg[i].y2, &seg[i].x);
sort(seg + , seg + + n);
for(int i = ; i <= n; i++)
{
qL = seg[i].y1 * ; qR = seg[i].y2 * ;
v = i;
query(, , maxn * );
update(, , maxn * );
} int ans = ;
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++) if(G[i][j])
for(int k = ; k <= n; k++) if(G[i][k] && G[j][k]) ans++;
printf("%d\n", ans);
} return ;
}
代码君