网页版传奇合击版本seo 页面链接优化
题目链接：
http://acm.split.hdu.edu.cn/showproblem.php?pid=5862
题目大意：给你很多平行X或Y轴的线段，求所有交点
解题思路：
对于平行与Y轴的直线按端点的X坐标排序，从最左边的平行于Y轴的遍历到最右边的平行于Y轴的。
对于一个平行于Y轴的线段L，一个平行于X轴的直线的左端点的若在在其右边那么肯定没交点，所以对所有平行于X轴的线段按左端点的X坐标排序，从头开始遍历直到遍历到左端点在L的右边停止，将符合条件的线段的右端点的X坐标压进优先队列里，并在对应的Y坐标加1，优先队列优越小的值优先级越高，压进之后判断队列顶的X是否大于线段L的X，若大于则相交，弹出所有小于线段X坐标的点，并在对应的Y坐标减1，答案数加上线段L两个Y坐标之间所有点的值的和。
再选下一个线段L1，从上次停的点继续遍历直到结束。
每个点最多压进一次，弹出一次，求区间和用树状数组维护。
复杂度n^2*logN*logN
这道题大众解法是按每条线段的左端点的X,Y坐标排序，平行于X轴则对应Y坐标加1，平行于Y轴则直接y1-y2的区间和。
AC代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#define RI(N) scanf("%d",&(N))
#define RII(N,M) scanf("%d %d",&(N),&(M))
#define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
#define mem(a) memset((a),0,sizeof(a))
using namespace std;
const int inf=1e9;
const int inf1=-1*1e9;
double EPS=1e-10;
typedef long long LL;
int n1=-1;
struct P
{int x1,y1;int x2,y2;void fu(int xx,int yy,int xxx,int yyy){x1=xx;y1=yy;x2=xxx;y2=yyy;if(x1>x2){swap(x1,x2);swap(y1,y2);}}
};
P p1[100005];//xP p2[100005];//yLL bit[500005],n;int x1[100005];
int x2[100005];
int y3[100005];
int y4[100005];bool cmp(P p1,P p2)
{if(p1.x1==p2.x1) return p1.x2<p2.x2;return p1.x1<p2.x1;
}LL sum(LL i)
{LL s=0;while(i>0){s+=bit[i];i-=i&-i;}return s;
}void add(LL i,LL x)
{while(i<=n1){bit[i]+=x;i+=i&-i;}
}struct ex
{int val;int poi;
};struct cmp1
{bool operator() (const ex a,const ex b) const{return a.val>b.val;}};priority_queue<ex,vector<ex>,cmp1> pq;int compress(int *x111,int *x222)
{vector<int> xs;for(int i=0; i<n; i++){for(int d=-1; d<=1; d++){int tx1=x111[i]+d,tx2=x222[i]+d;xs.push_back(tx1);xs.push_back(tx2);}}sort(xs.begin(),xs.end());xs.erase(unique(xs.begin(),xs.end()),xs.end());for(int i=0; i<n; i++){x111[i]=lower_bound(xs.begin(),xs.end(),x111[i])-xs.begin();x222[i]=lower_bound(xs.begin(),xs.end(),x222[i])-xs.begin();}return xs.size();
}bool cmp3(P p1,P p2)
{return p1.x1<p2.x1;
}int main()
{int T;RI(T);while(T--){RI(n);n1=-1;memset(bit,0,sizeof(bit));int p1length=0;int p2length=0;for(int i=0; i<n; i++){RII(x1[i],y3[i]);RII(x2[i],y4[i]);}compress(x1,x2);compress(y3,y4);for(int i=0; i<n; i++){x1[i]+=1;y3[i]+=1;x2[i]+=1;y4[i]+=1;if(y3[i]==y4[i]){n1=max(n1,y3[i]);p1[p1length++].fu(x1[i],y3[i],x2[i],y4[i]);}else p2[p2length++].fu(x1[i],y3[i],x2[i],y4[i]);}sort(p1,p1+p1length,cmp);sort(p2,p2+p2length,cmp3);LL ans=0;int poi=0;for(int i=0; i<p2length; i++){while(poi<p1length&&p1[poi].x1<=p2[i].x1){ex x;x.poi=p1[poi].y1;x.val=p1[poi].x2;pq.push(x);add(p1[poi].y1,1);poi++;}while(!pq.empty()&&(pq.top().val<p2[i].x1)){int x=pq.top().poi;add(x,-1);pq.pop();}LL y1=max(p2[i].y2,p2[i].y1);LL y2=min(p2[i].y2,p2[i].y1);if(y2-1==0) ans+=sum(y1);else ans+=sum(y1)-sum(y2-1);}printf("%I64d\n",ans);while(!pq.empty()){pq.pop();}}return 0;
}