实际上这种在左端点+1，右端点的下一个-1的题目已经见过很多了。适用于它的查询也是一个区间的。+1，-1相当于维护了一个区间的“高度”，因为查询也是区间的，只要这个区间某一个点的高度被+1了，那这个区间之前的更新就被“捕捉”到了，所以每次对这个区间求和就知道有多少个“交点”。
在这题，可以淡化横向线段的“线”，只保留两个端点，在y轴上，左端点（相当于开始）+1，右端点的下一个-1（结束）；遇到竖向的，就查询[y1,y2]之间有多少个1。这个更新查询很自然的想到用树状数组来做，因为y可以达到1<<32，而n只有1e5，所以要离散化。
网上看到写的特别好的代码，我也是仿照他写的
【代码】
复制代码
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/* *********************************************** Author :angon ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <stack> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; #define showtime fprintf(stderr,"time = %.15fn",clock() / (double)CLOCKS_PER_SEC) #define lld %I64d #define REP(i,k,n) for(int i=k;i<n;i++) #define REPP(i,k,n) for(int i=k;i<=n;i++) #define scan(d) scanf("%d",&d) #define scanl(d) scanf("%I64d",&d) #define scann(n,m) scanf("%d%d",&n,&m) #define scannl(n,m) scanf("%I64d%I64d",&n,&m) #define mst(a,k) memset(a,k,sizeof(a)) #define LL long long #define N 100005 #define mod 1000000007 inline int read(){int s=0;char ch=getchar();for(; ch<'0'||ch>'9'; ch=getchar());for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';return s;} struct node { int type,x,y1,y2; }t[N*2]; //点 int a[N*2]; bool cmp(node n1,node n2) { if(n1.x==n2.x) return n1.type<n2.type; return n1.x<n2.x; //按x排序 } int lowbit(int x) { return x & (-x); } int Maxn; int c[N*2]; void modify (int x,int add) { //在x位置加上add，要修改所有祖先 while(x<=Maxn) { c[x]+=add; x+=lowbit(x); } } int get_sum(int x) //统计前x项的和 { int ret=0; while(x>0) { ret+=c[x]; x-=lowbit(x); } return ret; } map<int,int>mp; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T; scan(T); while(T--) { int n,x1,y1,x2,y2; scan(n); int tot=0,all=0; while(n--) { scann(x1,y1);scann(x2,y2); if(x1==x2) //竖 { if(y1>y2) swap(y1,y2); t[tot++] = {1,x1,y1,y2}; //x1实际上没什么用 a[all++] = y1; a[all++] = y2; } else //横 { if(x1>x2) swap(x1,x2); t[tot++] = {0,x1,y1,1}; //左端点+1 t[tot++] = {0,x2+1,y2,-1}; //右端点的下一个-1 a[all++] = y1; } } sort(a,a+all); mp.clear(); Maxn=1; for(int i=0;i<all;i++) //树状数组是在y轴上操作的，对y离散化 { if(!mp[a[i]]) mp[a[i]]=Maxn++; } sort(t,t+tot,cmp); mst(c,0); LL ans=0; for(int i=0;i<tot;i++) //之前巧妙的把y2设为1和-1，可以少写很多判断 { if(t[i].type==0) { modify(mp[t[i].y1],t[i].y2); } else { ans += get_sum(mp[t[i].y2])-get_sum(mp[t[i].y1]-1); } } printf("%lldn",ans); } return 0; }
最后
以上就是优美小霸王最近收集整理的关于HDU 5862Counting Intersections (思维+树状数组）的全部内容，更多相关HDU内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复