POJ 1436 Horizontally Visible Segments (线段树+区间覆盖)
题意：给定一个二维平面，再给你n条垂直线条，如果有两条线段能用水平的线连接且不水平的线不接触其他线段，则说明这条两条线段可见，如果三条线段两两可见，则代表一个“三角形”，问给定线段集合中的“三角形”个数，
解题思路：线段树区间覆盖加统计，要把区间变为点数，所以所有点的 y 都要 乘 2 。 不会stl的童鞋伤不起，用链表统计，更新，最后在暴力找个数。
解题代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #define maxn 8005 5 int hs[maxn]; 6 struct op 7 { 8 int y1,y2,x; 9 } ops[maxn]; 10 int cmp(const void *a , const void *b) 11 { 12 return (*(op*)a).x - (*(op*)b).x; 13 } 14 struct li 15 { 16 int num ; 17 struct li*next; 18 }ths[maxn]; 19 struct li * newli() 20 { 21 struct li *p = (li*)malloc(sizeof(li)); 22 p->num = 0 ; 23 p->next = NULL; 24 return p ; 25 } 26 struct node 27 { 28 int l , r, m ; 29 int c ; 30 struct li head; 31 struct li* last; 32 } tree[maxn*8]; 33 int L(int c) 34 { 35 return 2*c; 36 } 37 int R(int c) 38 { 39 return 2*c + 1; 40 } 41 void Free(struct li *p) 42 { 43 if(p->next != NULL) 44 Free(p->next); 45 free(p); 46 } 47 void build(int c, int p , int v) 48 { 49 tree[c].l = p ; 50 tree[c].r = v; 51 tree[c].m = (p + v)/2; 52 tree[c].c = 0 ; 53 tree[c].head.next = NULL; 54 tree[c].head.num = 0 ; 55 tree[c].last = &tree[c].head; 56 if(p == v) 57 return ; 58 build(L(c),p,tree[c].m); 59 build(R(c),tree[c].m+1,v); 60 } 61 62 void Pushdown(int c) 63 { 64 65 if(tree[c].c != 0) 66 { 67 tree[L(c)].c = tree[c].c; 68 tree[R(c)].c = tree[c].c; 69 struct li *p; 70 p = newli(); 71 p->num = tree[c].c; 72 tree[L(c)].head.num = 1; 73 tree[L(c)].head.next = p ; 74 tree[L(c)].last = p; 75 p = newli(); 76 p->num = tree[c].c; 77 tree[R(c)].head.num = 1; 78 tree[R(c)].head.next = p ; 79 tree[R(c)].last = p; 80 tree[c].c = 0; 81 } 82 } 83 84 void Pushup(int c) 85 { 86 tree[c].head.num = tree[L(c)].head.num + tree[R(c)].head.num; 87 tree[L(c)].last->next = tree[R(c)].head.next; 88 tree[c].head.next = tree[L(c)].head.next; 89 if(tree[c].head.num == 0 ) 90 tree[c].last = &tree[c].head; 91 else if(tree[R(c)].head.num == 0) 92 tree[c].last = tree[L(c)].last; 93 else tree[c].last = tree[R(c)].last; 94 } 95 void update(int c, int p , int v, int value) 96 { 97 if(p <= tree[c].l &&v >= tree[c].r) 98 { 99 tree[c].c = value; 100 struct li *p = &tree[c].head; 101 for(int i = 1; i <= tree[c].head.num; i ++) 102 { 103 p = p->next ; 104 hs[p->num] = 1; 105 } 106 p = newli(); 107 p->num = value; 108 tree[c].head.num = 1; 109 tree[c].head.next = p ; 110 tree[c].last = p; 111 return ; 112 } 113 Pushdown(c); 114 if(v <= tree[c].m) update(L(c),p,v,value); 115 else if(p > tree[c].m) update(R(c),p,v,value); 116 else 117 { 118 update(L(c),p,tree[c].m,value); 119 update(R(c),tree[c].m+1,v,value); 120 } 121 Pushup(c); 122 } 123 int sum =0 ,n; 124 void fuck(int k) 125 { 126 for(int i = n;i >= 1;i --) 127 { 128 if(hs[i] == 1) 129 { 130 ths[k].num++; 131 struct li *p = newli(); 132 p->num = i ; 133 p->next = ths[k].next ; 134 ths[k].next = p ; 135 } 136 } 137 } 138 void F(int k) 139 { 140 struct li * p1 ,*p2 ; 141 p1 = &ths[k]; 142 bool visit[maxn] = {0}; 143 for(int i = 1; i <= ths[k].num ; i++) 144 { 145 p1 = p1->next; 146 visit[p1->num] = 1; 147 p2 = &ths[p1->num]; 148 for(int j= 1; j <= ths[p1->num].num; j ++) 149 { 150 p2 = p2->next; 151 if(visit[p2->num]) 152 sum ++; 153 } 154 } 155 } 156 int main() 157 { 158 int t ; 159 scanf("%d",&t); 160 while(t--) 161 { 162 sum = 0 ; 163 memset(tree,0,sizeof(tree)); 164 memset(ths,0,sizeof(ths)); 165 scanf("%d",&n); 166 for(int i =1 ; i <= n; i ++) 167 scanf("%d %d %d",&ops[i].y1,&ops[i].y2,&ops[i].x); 168 qsort(ops +1 , n, sizeof(op),cmp); 169 build(1,0,2*maxn); 170 for(int i= 1; i <= n; i ++) 171 { 172 memset(hs,0,sizeof(hs)); 173 update(1,ops[i].y1*2,ops[i].y2*2,i); 174 fuck(i); 175 F(i); 176 } 177 printf("%d ",sum); 178 } 179 return 0; 180 }