Description
As shown in the following figure, If another lighthouse is in gray area, they can beacon each other.
For example, in following figure, (B, R) is a pair of lighthouse which can beacon each other, while (B, G), (R, G) are NOT.
Input
1st line: N
2nd ~ (N + 1)th line: each line is X Y, means a lighthouse is on the point (X, Y).
Output
How many pairs of lighthourses can beacon each other
( For every lighthouses, X coordinates won't be the same , Y coordinates won't be the same )
Example
Input
3
2 2
4 3
5 1
Output
1
Restrictions
For 90% test cases: 1 <= n <= 3 * 105
For 95% test cases: 1 <= n <= 106
For all test cases: 1 <= n <= 4 * 106
For every lighthouses, X coordinates won't be the same , Y coordinates won't be the same.
1 <= x, y <= 10^8
Time: 2 sec
Memory: 256 MB
Hints
The range of int is usually [-231, 231 - 1], it may be too small.
第一眼看到这题时第一反应是用树状数组，但是发现数据太大，开不了10的6次方的二维数组，看了别人的博客才知道是用归并排序。
先理解一下题意，要求有多少对两两互相照亮的灯塔，怎么样才能是两两互相照亮的呢，两点的斜率为正，也就是按x递增排序，y也递增。
这样咱们就可以把n个点对x进行排序，找到y有多少对是顺序对就行，这就可以用到归并排序，在对左右两个集合合并时，i，j分别为左右两个集合的
指针，如果le[i]<ri[j]，正序对加上n2-j+1对，就这样去考虑。还有就是那里不能用<algorithm>，可以用stdlib.h里的qsort（）。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib> using namespace std; struct w
{
int x;
int y;
}k[];
int yi[];
long long ans;
int le[],ri[]; int cmp( const void *a ,const void *b)
{
return (*(w *)a).x > (*(w *)b).x ;
} void merge(int l,int mi,int r)
{
int i,j,p,n1=mi-l+,n2=r-mi;
const int MAX=; for (int i=;i<=n1;i++)
le[i]=k[l+i-].y;
for (int i=;i<=n2;i++)
ri[i]=k[mi+i].y; le[n1+]=MAX;ri[n2+]=MAX;
i=;j=;
for (int p=l;p<=r;p++)
{
if (le[i]>ri[j])
k[p].y=ri[j++];
else
{
k[p].y=le[i++];
ans+=n2-j+;
// cout <<ans<<endl;
}
}
}
void mergesort(int l,int r)
{
if (l==r)
return;
int mid=l+(r-l)/;
mergesort(l,mid);
mergesort(mid+,r);
merge(l,mid,r);
} int main()
{
int n;
cin>>n;
for (int i=;i<n;i++)
cin>>k[i].x>>k[i].y;
qsort(k,n,sizeof(k[]),cmp);
ans=;
mergesort(,n-);
cout <<ans<<endl;
return ;
}