POJ-1436___Horizontally Visible Segments —— 线段树

题目链接：点我啊╭(╯^╰)╮

题目大意：

     $n$ 条垂直于 $x$ 轴的线段，对于两条线段，如果有一条平行于 $x$ 轴的线穿过它们，并且不经过其他线段，则称这两条线段可见
     求有多少三元组线段，他们之间两两可见？

解题思路：

    所有线段按照 $x$ 排序后，进行枚举，这样对于每一条新的线段，就覆盖上去，每次覆盖如果原先已经有了覆盖的线段，那么这两条线段就可见，这样就解决了判断所有线段两两是否可见的问题
    最后枚举所有的三元组线段，ok

代码思路：

    既然是区间覆盖，肯定用线段树更好，这里的有个问题就是端点问题，在端点处怎么判断，很自然的就能想到区间$?2$，就避免了这个问题，可以好好想想

核心：对图形简化成线段区间的很好锻炼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 8010*2;
int t[maxn<<2];
bool link[maxn/2][maxn/2];struct Node{int y1, y2, x, id;Node(){}Node(int Y1,int Y2,int X,int Id):y1(Y1),y2(Y2),x(X),id(Id){}bool operator < (const Node &A)const {return x < A.x;}
} xd[maxn];void build(int l,int r,int rt) {t[rt] = -1;if(l==r) return;int m = (l+r)>>1;build(lson);build(rson);
}void pushdown(int rt) {if(t[rt]!=-1) {t[rt<<1] = t[rt<<1|1] = t[rt];t[rt] = -1;}
}void update(int L,int R,int C,int l,int r,int rt) {if(L<=l&&r<=R) {t[rt] = C;return ;}pushdown(rt);int m = (l+r)>>1;if(L<=m) update(L,R,C,lson);if(R>m) update(L,R,C,rson);
}void query(int L,int R,int C,int l,int r,int rt) {if(t[rt]!=-1) {link[t[rt]][C] = 1;return;}if(l==r) return;pushdown(rt);int m = (l+r)>>1;if(L<=m) query(L,R,C,lson);if(R>m) query(L,R,C,rson);
}int main() {int T, n, y1, y2, x;scanf("%d", &T);while(T--) {int ans=0;memset(link, 0, sizeof(link));scanf("%d", &n);build(0,maxn,1);for(int i=0; i<n; i++){scanf("%d%d%d", &y1, &y2, &x);y1<<=1, y2<<=1;xd[i] = Node(y1, y2, x, i);}sort(xd, xd+n);for(int i=0; i<n; i++){query(xd[i].y1,xd[i].y2,xd[i].id,0,maxn,1);update(xd[i].y1,xd[i].y2,xd[i].id,0,maxn,1);}for(int i=0; i<n; i++)for(int j=0; j<n; j++)if(link[i][j])for(int k=0; k<n; k++)if(link[i][k] && link[j][k])ans++;printf("%d\n", ans);}
}