首页 > 代码库 > POJ1436Horizontally Visible Segments线段树+lazy
POJ1436Horizontally Visible Segments线段树+lazy
判断3条线段是否联通,如果任意2条线段联通,则3条线段联通;开一个hash[i][j]保存第i条线段和第j条线段的关系,每次插入新的线段前都需要先判断此直线是否与前面的其他线段联通,再将这条线段插入;PS:要注意的一点是需要先对所有的线段关于x坐标进行排序,然后再按照熟顺序插入线段;
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 8010 int col[maxn*10]; bool hash[maxn][maxn]; struct bian { int y1,y2,x; }edge[maxn]; int cmp(bian a,bian b) { return a.x<b.x; } void pushdown(int rt) { if(~col[rt]) { col[rt<<1]=col[rt<<1|1]=col[rt]; col[rt]=-1; } } void build(int l,int r,int rt) { col[rt]=-1; if(l==r) return ; int m=(l+r)>>1; build(lson); build(rson); } void update(int L,int R,int cha,int l,int r,int rt) { if(L<=l&&R>=r) { col[rt]=cha; return ; } pushdown(rt); int m=(l+r)>>1; if(L<=m) update(L,R,cha,lson); if(R>m) update(L,R,cha,rson); } void query(int L,int R,int cha,int l,int r,int rt) { if(col[rt]!=-1) { hash[cha][col[rt]]=hash[col[rt]][cha]=cha; return ; } if(L>r||R<l) return ; int m=(l+r)>>1; if(L<=m) query(L,R,cha,lson); if(R>m) query(L,R,cha,rson); } int main() { int t,n,a,b,c; scanf("%d",&t); while(t--) { memset(hash,0,sizeof(hash)); int MAX=-1; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); edge[i].y1=a*2;edge[i].y2=b*2; edge[i].x=c; MAX=max(MAX,edge[i].y2); } sort(edge,edge+n,cmp); build(0,MAX,1); for(int i=0;i<n;i++) { query(edge[i].y1,edge[i].y2,i,0,MAX,1); update(edge[i].y1,edge[i].y2,i,0,MAX,1); } int ans=0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(!hash[i][j]) continue; for(int k=j+1;k<n;k++) { if(hash[i][k]&&hash[j][k]) ans++; } } } printf("%d\n",ans); } return 0; }
POJ1436Horizontally Visible Segments线段树+lazy
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。