我是靠谱客的博主 专一黑裤,这篇文章主要介绍HDU 5862 Counting Intersections(树状数组),现在分享给大家,希望可以做个参考。

题意:给你n条平行x或y轴的线段,保证没有公共端点 没有覆盖,问有多少交点。


思路:对所有线段按x坐标排序,将y坐标离散化,将水平线段拆成两部分,左端点一个,右端点+1一个, 枚举所有线段遇到水平线段的左端点,对应y坐标在树状数组中的值+1,遇到水平线段的(右端点+1)时,将其对应y坐标在树状数组中的值-1.遇到竖直线段时,查询其纵坐标区间的和,也就是条竖直线段能产生的交点的个数.


代码:

复制代码
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
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5+5; struct node { int type, x, y1, y2; node() {} node(int tt, int xx, int yy1, int yy2): type(tt), x(xx), y1(yy1), y2(yy2) {} bool operator < (const node &a) const { if(x == a.x) return type < a.type; else return x < a.x; } }a[maxn]; int Hash[maxn], tree[maxn]; int lowbit(int x) { return x&(-x); } void update(int pos, int val) { while(pos < maxn) { tree[pos] += val; pos += lowbit(pos); } } int query(int pos) { int res = 0; while(pos) { res += tree[pos]; pos -= lowbit(pos); } return res; } int main(void) { int _, n, cnt, hash_cnt; cin >> _; while(_--) { cnt = hash_cnt = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); if(y1 == y2) { if(x1 > x2) swap(x1, x2); a[cnt++] = node(0, x1, y1, 1); a[cnt++] = node(0, x2+1, y1, -1); Hash[hash_cnt++] = y1; } else { if(y1 > y2) swap(y1, y2); a[cnt++] = node(1, x1, y1, y2); Hash[hash_cnt++] = y1; Hash[hash_cnt++] = y2; } } sort(Hash, Hash+hash_cnt); int id = 1; map<int, int> m; for(int i = 0; i < hash_cnt; i++) if(!m[Hash[i]]) m[Hash[i]] = id++; sort(a, a+cnt); memset(tree, 0, sizeof(tree)); ll ans = 0; for(int i = 0; i < cnt; i++) { if(a[i].type) ans += query(m[a[i].y2])-query(m[a[i].y1]-1); else update(m[a[i].y1], a[i].y2); } printf("%lldn", ans); } return 0; }


最后

以上就是专一黑裤最近收集整理的关于HDU 5862 Counting Intersections(树状数组)的全部内容,更多相关HDU内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(92)

评论列表共有 0 条评论

立即
投稿
返回
顶部