传送门：HDU5862
因为题目已经说明所有的线段都是平行于坐标轴的
那么,线段无外乎两种:①平行于x轴;②平行于y轴
那交点必定只有竖向与横向的线段才会产生
另外,此题数据规模显然是不允许我们进行O(n^2)的暴力求解
那我们可以将横向的线段与竖向线段分开处理
对于横向的线段,我们只保留端点
再按x从小到大排序,x相等的情况下,左端点优先于右端点
而竖向的线段同样按x从小到大排序,但是不拆分成两个端点,而是保留整条线段
然后枚举竖向线段,将小于该竖向线段横坐标的所有点进行处理
若点为左端点,则在其对应的值处的树状数组做+1操作,若为右端点,则做-1操作
这保证了对于第i条竖向线段,当前树状数组中记录了横坐标横跨该竖向线段的线段数量（至于相不相交就要看横线的纵坐标在不在竖线的范围内了）
以上转自：http://blog.csdn.net/just_sort/article/details/52244981
蒟蒻刚学扫描线，感觉上面这篇题解介绍的挺到位的，让我也大致了解了扫描线的思想，所以就无耻的CV了。
代码：
#include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<map> #define ll long long #define pi acos(-1) #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef pair<int,int>P; const int MAXN=400010; struct node1{ int x,y,type; bool operator < (node1 a)const { if(x==a.x) return type<a.type; return x<a.x; } }r[MAXN]; struct node2{ int x1,y1,x2,y2; bool operator < (node2 a)const { return x1<a.x1; } }c[MAXN],seg[MAXN]; ll bit[MAXN]; int Hash[MAXN]; ll b_sum(int i) { ll ans=0; while(i>0) { ans+=bit[i]; i-=i&-i; } return ans; } void b_add(int i,int x) { while(i<MAXN) { bit[i]+=x; i+=i&-i; } } int main() { int T,n,cnt; scanf("%d",&T); while(T--) { cnt=1;//cnt初始化为1是因为树状数组下标从1开始 memset(bit,0,sizeof(bit)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&seg[i].x1,&seg[i].y1,&seg[i].x2,&seg[i].y2); if(seg[i].x1>seg[i].x2||seg[i].y1>seg[i].y2) { swap(seg[i].x1,seg[i].x2); swap(seg[i].y1,seg[i].y2); } Hash[cnt++]=seg[i].x1; Hash[cnt++]=seg[i].y1; Hash[cnt++]=seg[i].x2; Hash[cnt++]=seg[i].y2; } sort(Hash+1,Hash+cnt); cnt=unique(Hash+1,Hash+cnt)-Hash; int x1,y1,x2,y2,cnt1=0,cnt2=0; for(int i=1;i<=n;i++) { x1=lower_bound(Hash+1,Hash+cnt,seg[i].x1)-Hash; y1=lower_bound(Hash+1,Hash+cnt,seg[i].y1)-Hash; x2=lower_bound(Hash+1,Hash+cnt,seg[i].x2)-Hash; y2=lower_bound(Hash+1,Hash+cnt,seg[i].y2)-Hash; if(x1==x2) c[cnt2++]=node2{x1,y1,x2,y2}; if(y1==y2) { r[cnt1].x=x1,r[cnt1].y=y1,r[cnt1++].type=0; r[cnt1].x=x2,r[cnt1].y=y2,r[cnt1++].type=1; } } sort(r,r+cnt1); sort(c,c+cnt2); ll ans=0; for(int i=0,j=0;i<cnt2;i++) { while(j<cnt1&&(r[j].x<c[i].x1||(r[j].x==c[i].x1&&r[j].type==0)))//注意横线右端点和竖线相交的情况不能进入while { if(r[j].type) b_add(r[j].y,-1); else b_add(r[j].y,1); j++; } ans+=b_sum(c[i].y2)-b_sum(c[i].y1-1);//在竖线纵坐标范围内 } printf("%lld\n",ans); } return 0; }
