这道题最终就是问，两两可见的三条线段组有多少组。所谓两两可见，指的是某一条横线可以连接到两条线段，并且中途不会碰到其他线段。
很显然又是一道区间染色的题目嘛，关于区间染色的解法，不多说了，这里说关键的！
这题就sample来说，按它给的数据来建树的话，最右边的和最左边的是无法触碰到一起的，因为第二根线段和第三根线段之间只留下了[2,3]这样的小缝隙，而这样的小缝隙在线段树建树的过程中，是会被二分忽略掉的。看图
上面黑色的，就是题目所给的sample所对应的坐标系上的图样，而下面的红色的，就是上面的黑色的在线段树中所对应的图样。
很显然最右边的竖线和第一根竖线相连时[2,3]这条缝隙给忽略过去了！ 导致它们无法相连...
解决的办法是将所给的所有数据都乘以2，这样就空隙[2,3]就会变成区间[4,6]，这样就可以过去了！
将所给的竖直线段从左到右排序后一次对线段树进行染色，染色之前进行一次查找，看看新的颜色能够更新那些旧的颜色，能更新，就说明两两可见！最后穷举每条边即可！
View Code 1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 struct node 9 { 10 int l; 11 int r; 12 int cover; 13 }; 14 15 node tree[100000]; 16 int n; 17 int v[8002]; 18 19 struct Line 20 { 21 int x; 22 int y1; 23 int y2; 24 }; 25 26 Line line[8001]; 27 28 int cmp(Line a,Line b) 29 { 30 return a.x
map[8001]; 34 35 void build(int i,int l,int r) 36 { 37 tree[i].l=l; 38 tree[i].r=r; 39 tree[i].cover=0; 40 if(l==r) 41 return; 42 int mid=(l+r)/2; 43 build(2*i,l,mid); 44 build(2*i+1,mid+1,r); 45 } 46 47 void updata(int i,int l,int r,int w) 48 { 49 if(tree[i].l>r || tree[i].r
=l && tree[i].r<=r) 52 { 53 tree[i].cover=w; 54 return; 55 } 56 if(tree[i].cover!=-1) 57 { 58 tree[2*i].cover=tree[2*i+1].cover=tree[i].cover; 59 tree[i].cover=-1; 60 } 61 updata(2*i,l,r,w); 62 updata(2*i+1,l,r,w); 63 } 64 65 void find(int i,int l,int r,int x) 66 { 67 if(tree[i].l>r || tree[i].r =1;i--) //穷举每一条边 107 { 108 for(j=0;j!=map[i].size();j++) 109 { 110 a=map[i][j]; 111 for(k=0;k!=map[a].size();k++) 112 { 113 b=map[a][k]; 114 for(l=0;l!=map[i].size();l++) 115 if(map[i][l]==b) 116 ans++; 117 } 118 } 119 } 120 printf("%d\n",ans); 121 } 122 return 0; 123 }