（线段树）poj1436-Horizontally Visible Segments

There is a number of disjoint vertical line segments in the plane. We say that two segments are horizontally visible if they can be connected by a horizontal line segment that does not have any common points with other vertical segments. Three different vertical segments are said to form a triangle of segments if each two of them are horizontally visible. How many triangles can be found in a given set of vertical segments?

Task

Write a program which for each data set:

reads the description of a set of vertical segments,

computes the number of triangles in this set,

writes the result.

Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.

The first line of each data set contains exactly one integer n, 1 <= n <= 8 000, equal to the number of vertical line segments.

Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:

yi', yi'', xi - y-coordinate of the beginning of a segment, y-coordinate of its end and its x-coordinate, respectively. The coordinates satisfy 0 <= yi' < yi'' <= 8 000, 0 <= xi <= 8 000. The segments are disjoint.

Output

The output should consist of exactly d lines, one line for each data set. Line i should contain exactly one integer equal to the number of triangles in the i-th data set.

Sample Input

Sample Output

1

就是区间染色问题。用线段树维护每个区间的颜色，对于读入数据处理排序为从左到右update，x坐标其实无关紧要。用二维bool数组记录两个线段是否水平可视，枚举即可求得答案。

  1 #include <iostream>
  2 //#include<bits/stdc++.h>
  3 #include <stack>
  4 #include <queue>
  5 #include <map>
  6 #include <set>
  7 #include <cstdio>
  8 #include <cstring>
  9 #include <algorithm>
 10 using namespace std;
 11 typedef long long ll;
 12 typedef unsigned long long ull;
 13 const int MAX=16000;
 14 int d,n;
 15 bool link[8001][8001];
 16 struct node
 17 {
 18     int col;
 19 }st[20*MAX];
 20 void init(int l,int r,int k)
 21 {
 22     st[k].col=0;
 23     if(l==r)
 24         return;
 25     init(l,(l+r)/2,2*k);
 26     init((l+r)/2+1,r,2*k+1);
 27 }
 28 void pushdown(int k)
 29 {
 30     if(st[k].col==0)
 31         return;
 32     st[2*k].col=st[2*k+1].col=st[k].col;
 33     st[k].col=0;
 34 }
 35 void update(int l,int r,int L,int R,int k,int j)//[l,r]是目标区间 [L,R]是当前区间,j是向左看的线的编号
 36 {
 37     if(L>=l&&R<=r)
 38     {
 39         st[k].col=j;
 40         return;
 41     }
 42     if(L==R)
 43         return;
 44     pushdown(k);
 45     if(l<=(L+R)/2)
 46         update(l,r,L,(L+R)/2,2*k,j);
 47     if(r>(L+R)/2)
 48         update(l,r,(L+R)/2+1,R,2*k+1,j);
 49 }
 50 void query(int l,int r,int L,int R,int k,int j)//[L,R]是当前区间,[l,r]是目标区间
 51 {
 52     if(st[k].col)
 53     {
 54         link[st[k].col][j]=true;
 55         return;
 56     }
 57     if(L==R)
 58         return;
 59     if(l<=(L+R)/2)
 60         query(l,r,L,(L+R)/2,2*k,j);
 61     if(r>(R+L)/2)
 62         query(l,r,(L+R)/2+1,R,2*k+1,j);
 63 }
 64 struct re
 65 {
 66     int x,xia,shang;
 67 }z[MAX];
 68 bool cmp(re aa,re bb)
 69 {
 70     if(aa.x!=bb.x)
 71     return aa.x<bb.x;
 72     else
 73         return aa.xia<bb.xia;
 74 }
 75 int main()
 76 {
 77     scanf("%d",&d);
 78     int x,s,i,tem;
 79     while(d--)
 80     {
 81         scanf("%d",&n);
 82         init(0,MAX,1);
 83         memset(link,false,sizeof(link));
 84 //        for(i=1;i<=n;i++)
 85 //        {
 86 //            scanf("%d %d %d",&x[i],&s,&tem);
 87 //            update(2*x,2*s,0,MAX,1,i);
 88 //        }
 89         for(i=1;i<=n;i++)
 90             scanf("%d %d %d",&z[i].xia,&z[i].shang,&z[i].x);
 91         sort(z+1,z+n+1,cmp);
 92         for(i=1;i<=n;i++)
 93             {
 94                 query(2*z[i].xia,2*z[i].shang,0,MAX,1,i);
 95                 update(2*z[i].xia,2*z[i].shang,0,MAX,1,i);
 96 
 97             }
 98         int j,k,q;
 99         int an=0;
100         for(i=1;i<=n;i++)
101         {
102             for(j=i+1;j<=n;j++)
103             {
104                 if(link[i][j])
105                 {
106 //                    printf("%d %d i:%d %d %d j:%d %d %d
",i,j,2*z[i].xia,2*z[i].shang,z[i].x,2*z[j].xia,2*z[j].shang,z[j].x);
107                     for(q=i+1;q<j;q++)
108                     {
109                         if(link[i][q]&&link[q][j])
110                             an++;
111                     }
112                 }
113             }
114         }
115         printf("%d
",an);
116     }
117 }