poj 1436 Horizontally Visible Segments

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

题意:给出一系列的竖直线段,给出线段上下端点的坐标和横坐标。找一条横线放在两条竖直线之间(且两者间没有其它竖直线被穿过),那么说这两条竖直线是“可见”的;如果有3条直线,任意两两可见,就是这3条直线组成一个三元组。注意,水平横线的高低可以是浮点数。题目是问你,这些竖直直线中能找到多少三元组。

sample的这样的,(0,3,1)这条直线和(0,4,4)可见的,但水平线位于[2,3]这些浮点数位置的时候,可以刚好仅穿过这两条竖线而不穿过其他的。(0,3,1)和(3,4,2)是可见的,横线位于高度3时刚好穿过两条直接且中间没有其他线。而(3,4,2)和(0,4,4)也是可见的,并且中间没有其他线阻碍。即(0,3,1),(3,4,2),(0,4,4)这3条直线组成一个三元组

这题一开始觉得很简单,好像不需要线段树,后来想想才明白,在判断可见时,就是利用了线段树,类似于染色问题(贴墙纸问题)那样。

  1. 先将所有直线按横坐标升序排序。然后从左到右插入线段。线段代表的区间就是它的两个上下端点,总区间是[0,Max]。
  2. 插入一条线段的时候,如果准备插入的位置之前已经有线段插入了,那么就是说,这两者间是可见的(因为已经按照从左到右顺序插入了,中间不会有其他线段)。那么就记录一个可见关系edge[i][j]。那么新的线段插入后,就覆盖了这个区间,更新这个区间的信息,记录当前是被哪条线段覆盖的。
  3. 看懂上面后,简易来说就是,每次准备一条新的线段的时候,先看看它要插入的地方之前被什么线段线段覆盖(代码中的query函数),那么加边;然后自己盖上去(代码中的updata函数)。时刻维护的信息就是,一段区间当前被哪条线段覆盖

直接用一个矩阵来保存,最后O(n^3)找出所有合法三元组,跑了1500ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 8010
#define MAX 16010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n;
struct SegTree{
int l,r;
int lazy;
SegTree(){}
SegTree(int _l,int _r,int _lazy){
l = _l; r = _r; lazy = _lazy;
}
int mid(){
return (l+r)>>1;
}
}t[4*MAX];
struct Seg{
int y1,y2,x;
}s[N];
bool edge[N][N];

bool cmp(Seg a ,Seg b){
return a.x < b.x;
}

void build(int rt,int a,int b){
t[rt] = SegTree(a,b,-1);
if(a == b) return ;
int mid = t[rt].mid();
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
}

void PushDown(int rt){
if(t[rt].lazy != -1){
t[lson(rt)].lazy = t[rson(rt)].lazy = t[rt].lazy;
t[rt].lazy = -1;
}
}

void updata(int rt,int a,int b,int id){
if(t[rt].l == a && t[rt].r == b){
t[rt].lazy = id;
return ;
}
PushDown(rt);
int mid = t[rt].mid();
if(b <= mid)
updata(lson(rt),a,b,id);
else if(a > mid)
updata(rson(rt),a,b,id);
else{
updata(lson(rt),a,mid,id);
updata(rson(rt),mid+1,b,id);
}
}

void query(int rt,int a,int b,int id){
if(t[rt].lazy != -1){
edge[t[rt].lazy][id] = true;
return ;
}
if(t[rt].l == t[rt].r) return ;
int mid = t[rt].mid();
if(b <= mid)
query(lson(rt),a,b,id);
else if(a > mid)
query(rson(rt),a,b,id);
else{
query(lson(rt),a,mid,id);
query(rson(rt),mid+1,b,id);
}
}

int main(){
int cas;
scanf("%d",&cas);
while(cas--){
int Max = -1;
scanf("%d",&n);
cl(edge,false);
for(int i = 0; i < n; i++){
scanf("%d%d%d",&s[i].y1,&s[i].y2,&s[i].x);
s[i].y1 <<= 1; s[i].y2 <<= 1;
Max = max(Max,max(s[i].y1,s[i].y2));
}
sort(s,s+n,cmp);
build(1,0,Max);
for(int i = 0; i < n; i++){
query(1,s[i].y1,s[i].y2,i);
updata(1,s[i].y1,s[i].y2,i);
}
/*
puts("Seg");
for(int i = 0; i < n; i++)
printf("%d %d %d\n",s[i].y1,s[i].y2,s[i].x);
puts("Edge");
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
if(edge[i][j])
printf("%d -- %d\n",i,j);
*/
int res = 0;
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
if(edge[i][j])
for(int k = j+1; k < n; k++)
if(edge[i][k] && edge[j][k]){
//printf("%d - %d - %d\n",i,j,k);
res++;
}
printf("%d\n",res);
}
return 0;
}

用一个邻接表来保存可见关系,但是会有重复,所以还是用了二维的矩阵的判重(可以用一维的数组来判重的,道理就不说了,比较容易想)。时间会提高到500ms,如果一维判重可以到100ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define N 8010
#define MAX 16010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int n;
struct SegTree{
int l,r;
int lazy;
SegTree(){}
SegTree(int _l,int _r,int _lazy){
l = _l; r = _r; lazy = _lazy;
}
int mid(){
return (l+r)>>1;
}
}t[4*MAX];
struct Seg{
int y1,y2,x;
}s[N];
vector<int>edge[N];
bool map[N][N];

bool cmp(Seg a ,Seg b){
return a.x < b.x;
}

void build(int rt,int a,int b){
t[rt] = SegTree(a,b,-1);
if(a == b) return ;
int mid = t[rt].mid();
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
}

void PushDown(int rt){
if(t[rt].lazy != -1){
t[lson(rt)].lazy = t[rson(rt)].lazy = t[rt].lazy;
t[rt].lazy = -1;
}
}

void updata(int rt,int a,int b,int id){
if(t[rt].l == a && t[rt].r == b){
t[rt].lazy = id;
return ;
}
PushDown(rt);
int mid = t[rt].mid();
if(b <= mid)
updata(lson(rt),a,b,id);
else if(a > mid)
updata(rson(rt),a,b,id);
else{
updata(lson(rt),a,mid,id);
updata(rson(rt),mid+1,b,id);
}
}

void query(int rt,int a,int b,int id){
if(t[rt].lazy != -1){
if(!map[t[rt].lazy][id]){ //避免edge邻接表里面存入相同的边
map[t[rt].lazy][id] = true;
edge[t[rt].lazy].pb(id);
}
return ;
}
if(t[rt].l == t[rt].r) return ;
int mid = t[rt].mid();
if(b <= mid)
query(lson(rt),a,b,id);
else if(a > mid)
query(rson(rt),a,b,id);
else{
query(lson(rt),a,mid,id);
query(rson(rt),mid+1,b,id);
}
}

int main(){
int cas;
scanf("%d",&cas);
while(cas--){
int Max = -1;
scanf("%d",&n);
for(int i = 0; i < n; i++){
edge[i].clear();
for(int j = 0; j < n; j++) map[i][j] = false;
scanf("%d%d%d",&s[i].y1,&s[i].y2,&s[i].x);
s[i].y1 <<= 1; s[i].y2 <<= 1;
Max = max(Max,max(s[i].y1,s[i].y2));
}
sort(s,s+n,cmp);
build(1,0,Max);
for(int i = 0; i < n; i++){
query(1,s[i].y1,s[i].y2,i);
updata(1,s[i].y1,s[i].y2,i);
}
int res = 0;
for(int i = 0; i < n; i++){
int sizei = edge[i].size();
for(int ii = 0; ii < sizei; ii++){
int j = edge[i][ii];
int sizej = edge[j].size();
for(int jj = 0; jj < sizej; jj++){
int k = edge[j][jj];
if(map[i][k] && map[j][k])
res++;
}
}
}
printf("%d\n",res);
}
return 0;
}