稻草人（bzoj 4237）

Description

JOI村有一片荒地，上面竖着N个稻草人，村民们每年多次在稻草人们的周围举行祭典。

有一次，JOI村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件：

田地的形状是边平行于坐标轴的长方形；

左下角和右上角各有一个稻草人；

田地的内部(不包括边界)没有稻草人。

给出每个稻草人的坐标，请你求出有多少遵从启示的田地的个数

Input

第一行一个正整数N，代表稻草人的个数

接下来N行，第i行(1<=i<=N)包含2个由空格分隔的整数Xi和Yi，表示第i个稻草人的坐标

Output

输出一行一个正整数，代表遵从启示的田地的个数

Sample Input

4
0 0
2 2
3 4
4 3

Sample Output

HINT

所有满足要求的田地由下图所示：

1<=N<=2*10^5

0<=Xi<=10^9(1<=i<=N)

0<=Yi<=10^9(1<=i<=N)

Xi(1<=i<=N)互不相同。

Yi(1<=i<=N)互不相同。

/*
  网上说这是一道cdq分治
  我们对于y坐标进行分治，对于某一段先按照x坐标排序，考虑上半部分对于下半部分的影响。 
  考虑上半部分某个点i，如果它能作为右上的点与下半部分的某个点形成长方形，那么必须保证在他们之间没有某个点j，使得x[j]<x[i]&&y[j]<y[i]，画图可知，我们可以在上半部分维护一个y递增的单调栈，下半部分维护一个y递减的单调栈，这样能保证一一对应，然后二分求出第一个满足条件的坐标。 
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 200010
#define lon long long
using namespace std;
int n,p[N],q[N];lon ans;
struct node{int x,y;}a[N],b[N];
bool cmpy(const node&s1,const node&s2){return s1.y<s2.y;}
int find(int x,int l,int r){
    while(l+1<r){
        int mid=l+r>>1;
        if(a[q[mid]].x<x) l=mid;
        else r=mid;
    }
    return l;
}
void solve(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    solve(l,mid);solve(mid+1,r);
    int tp1=0,tp2=0,i,j=l,k;
    for(i=mid+1;i<=r;i++){
        while(tp1&&a[i].y<a[p[tp1]].y)tp1--;
        p[++tp1]=i;
        for(;a[j].x<a[i].x&&j<=mid;j++){
            while(tp2&&a[j].y>a[q[tp2]].y)tp2--;
            q[++tp2]=j;
        }
        ans+=tp2-find(a[p[tp1-1]].x,0,tp2+1);
    }
    j=l;k=mid+1;
    for(i=l;i<=r;i++)
        b[i]=((j<=mid&&a[j].x<a[k].x)||k>r)?a[j++]:a[k++];
    for(i=l;i<=r;i++)a[i]=b[i];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmpy);
    solve(1,n);
    cout<<ans;
    return 0;
}