思路{
想怎么统计呢,发现在第一次一定算完了所有的点.那么现在问题变成了算有多少个点满足上下左右都有点.
不妨转化为线段求交.抽象成一些横线,竖线.竖线交横线产生贡献.
怎么统计贡献呢???
好的,用从下往上的扫描线就可以了,
碰到竖线下端点,x坐标位置+1,上端点的话-1.遇到横线统计一段x之内的答案就可以了
注意同一高度线段的扫描顺序可以把竖线拆成两个点.
}
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define N 1000001
#define lowbit ( (i) & (-i) )
#define LL long long
using namespace std;
struct point{
int x,y;
void read(){scanf("%d%d",&x,&y);}
}p[N];
struct seg{
int h1,h2,h3,flag;
seg() {}
seg(int x,int y,int z,int a):h1(x),h2(y),h3(z),flag(a) {}
}s[N];
int tree[N],n,tot,sz,sub[N];
void Insert(int pos,int num){for(int i=pos;i<=n;i+=lowbit)tree[i]+=num;}
int Query(int pos){int sum(0);for(int i=pos;i;i-=lowbit)sum+=tree[i];return sum;}
int find(int x){
return lower_bound(sub+1,sub+sz+1,x)-sub;
}
void link(int ff,int l,int r,int h){//0横线,1竖线
if(!ff){
s[++tot]=seg(find(l),find(r),h,0);
}else {
int X=find(h);
s[++tot]=seg(X,X,l,1);
s[++tot]=seg(X,X,r,-1);
}
}
bool comp(const point & a,const point & b){return a.x==b.x?a.y<b.y:a.x<b.x;}
bool Comp(const point & a,const point & b){return a.y==b.y?a.x<b.x:a.y<b.y;}
bool COMP(const seg & a,const seg & b){
if(a.h3!=b.h3)return a.h3<b.h3;
return a.flag<b.flag;
}
void build(){
sort(p+1,p+n+1,comp);
for(int i=2;i<=n;++i)
if(p[i].x==p[i-1].x)
link(1,p[i-1].y,p[i].y,p[i].x);
sort(p+1,p+n+1,Comp);
for(int i=2;i<=n;++i)
if(p[i].y==p[i-1].y)
link(0,p[i-1].x,p[i].x,p[i].y);
sort(s+1,s+tot+1,COMP);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)p[i].read(),sub[++sub[0]]=p[i].x;
sort(sub+1,sub+sub[0]+1);
sz=unique(sub+1,sub+sub[0]+1)-sub-1;
build();LL Ans(0);
for(int i=1;i<=tot;++i){
if(!s[i].flag)Ans+=Query(s[i].h2-1)-Query(s[i].h1);
else Insert(s[i].h1,s[i].flag);
}cout<<Ans+n;
return 0;
}
原文：http://www.cnblogs.com/zzmmm/p/7487423.html