POJ 1436 Horizontally Visible Segments(线成段更新)

题目大意：

n条线段，问有多少三条线段组能两两可见，可见的定义就是他们之间没有夹着别的线段，方然中间有线段的话是可以错开的。

思路：

一个简单的思路，

现有三条线

0 1 1

0 1 2

0 1 3

既然第二条线覆盖了第一条，那么第三条永远不会跟第一条可见了。所以每次更新区间的时候直接覆盖就可以了

那么我们线段树上记录的就是覆盖这个区间的线段的编号。

要把Y乘以2...因为线段树上记录的是线段不是端点。

0,4,1 和 0,2,2 和 3,4,2

这个数据就能说明问题了，如果不乘以2 那么 第二条 和 第三条就把 x=2 这一段堵死了，其实应该还有2-3这个一段的。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e #define maxn 8005 using namespace std; bool map[maxn][maxn]; int cov[maxn<<3]; struct line { int st,ed,x; bool operator < (const line &cmp)const { return x
      
       >1; build(lson); build(rson); } void update(int num,int s,int e,int l,int r,int val) { if(l<=s && r>=e) { cov[num]=val; return; } pushdown(num); int mid=(s+e)>>1; if(l<=mid)update(lson,l,r,val); if(r>mid)update(rson,l,r,val); } void query(int num,int s,int e,int l,int r,int id) { if(cov[num]!=-1) { map[cov[num]][id]=true; return; } if(s==e)return; pushdown(num); int mid=(s+e)>>1; if(l<=mid)query(lson,l,r,id); if(r>mid)query(rson,l,r,id); } int main() { int T; scanf("%d",&T); while(T--) { memset(map,false,sizeof map); int n; scanf("%d",&n); int m=-1; for(int i=1;i<=n;i++) { scanf("%d%d%d",&L[i].st,&L[i].ed,&L[i].x); L[i].st*=2; L[i].ed*=2; m=max(m,L[i].ed); } sort(L+1,L+1+n); build(1,1,16000); for(int i=1;i<=n;i++) { query(1,1,m,L[i].st,L[i].ed,i); update(1,1,m,L[i].st,L[i].ed,i); } int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(map[i][j]) { for(int k=1;k<=n;k++) if(map[i][k] && map[j][k])ans++; } printf("%d\n",ans); } return 0; }