C++11(clang++ 3.9) 解法, 执行用时: 410ms, 内存消耗: 2424K, 提交时间: 2019-10-24 17:49:59

#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=200010;
inline const int read(){
   register int f=1,x=0;
   register char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
   return f*x;
}
struct point{
   int x,y;
}aa[maxn];
long long ans;
int s1[maxn],s2[maxn],n;
inline bool cmpx(point a,point b){return a.x<b.x;}
inline bool cmpy(point a,point b){return a.y<b.y;}
void cdqz(int lf,int rg){
   if(lf==rg) return;
   int mid=(lf+rg)>>1,j=lf,top1=0,top2=0;
   cdqz(lf,mid),cdqz(mid+1,rg);
   sort(aa+lf,aa+mid+1,cmpx),sort(aa+mid+1,aa+rg+1,cmpx);
   for(int i=mid+1;i<=rg;i++){
       while(top1&&aa[s1[top1]].y>=aa[i].y) top1--;
	   s1[++top1]=i;
	   while(aa[j].x<aa[i].x&&j<=mid){
	      while(top2&&aa[s2[top2]].y<=aa[j].y) top2--;
	      s2[++top2]=j;
	      j++;
	   }
	   int l=1,r=top2,std=aa[s1[top1-1]].x,pos=-1;
	   while(l<=r){
	       int mid=(l+r)>>1;
	       if(aa[s2[mid]].x>std) pos=mid,r=mid-1;
	       else l=mid+1;
	   }
	   if(pos!=-1) ans+=top2-pos+1; 
   }
}
int main(){
   n=read();
   aa[0].x=aa[0].y=-1;
   for(register int i=1;i<=n;i++) aa[i].x=read(),aa[i].y=read();
   sort(aa+1,aa+n+1,cmpy);
   cdqz(1,n);
   printf("%lld\n",ans);
}