题面

$JOI$村有一片荒地，上面竖着$N$个稻草人，村民们每年多次在稻草人们的周围举行祭典。有一次，$JOI$村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件：田地的形状是边平行于坐标轴的长方形；左下角和右上角各有一个稻草人；田地的内部(不包括边界)没有稻草人。给出每个稻草人的坐标，请你求出有多少遵从启示的田地的个数.

简化题面

给出N个点，求使得两点为矩阵左下角右上角且形成矩阵内无点的点对数量。

思路

首先想到分治。（别问我为什么）

考虑一种类似于$CDQ$的分治。首先根据$x$排序，一个一个一个一个一个排序好。然后CDQ$(1,n)$每次用$mid$划分，我们把$y$大于$mid$的分到上方，小于的放到下方，那么答案一定是如图所示的这样。

考虑每次用右上角的点去找左下角的点对，发现可能的答案一定出现在下方$x$从小到大依次加入根据$y$维护的单调下降栈中。但是可能的答案一定全部可行吗?

我们发现了还要维护在上方的该点左边第一个比它低的点，这个的话维护一个$y$单调上升的栈就可以了/kk。然后用这个点的$x$坐标在下方的单调下降栈里面二分。减去被遮挡住的点即可。

然后递归分治$[l,mid]$$[mid+1,r]$求解即可。

Ps.上方可能与左下角产生贡献的点定在上方根据$y$单调下降的栈中，但是我们对于每一个上方的点都操作下也是可以的，因为那些不在上面的点贡献会被挡掉减掉。

代码

#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
long long ans;
int N,up_top,down_top;
int Y[MAXN],up_stack[MAXN],down_stack[MAXN],lsh[MAXN];
struct node{int x,y;}P[MAXN];
bool cmp(node a,node b){return a.x<b.x;}
int Find(int l,int r,int v){
	int ret=r+1;
    while(l<=r)
	{
        int mid=(l+r)>>1;
        if(down_stack[mid]>v) ret=mid,r=mid-1;
        else l=mid+1;
    }
    return ret;
}
void CDQ(int l,int r){
    int LY[MAXN],RY[MAXN],up_top=0,down_top=0;
    if(l==r)return;
    int mid=(l+r)>>1,L=l,R=mid+1;
    for(int i=l;i<=r;i++){
        if(Y[i]>mid){
            while(up_top&&Y[up_stack[up_top]]>Y[i]) up_top--;
            up_stack[++up_top]=i; RY[R++]=Y[i];
            ans+=down_top-Find(1,down_top,up_stack[up_top-1])+1;
        }
        else{
            while(down_top&&Y[down_stack[down_top]]<Y[i]) down_top--;
            down_stack[++down_top]=i; LY[L++]=Y[i];
        }
    }
    for(int i=l;i<=mid;i++) Y[i]=LY[i];
    for(int i=mid+1;i<=r;i++) Y[i]=RY[i];
    CDQ(l,mid); CDQ(mid+1,r);
}
int main(){
    
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d%d",&P[i].x,&P[i].y),lsh[i]=P[i].y;
    sort(P+1,P+N+1,cmp); sort(lsh+1,lsh+N+1);
    for(int i=1;i<=N;i++) Y[i]=lower_bound(lsh+1,lsh+N+1,P[i].y)-lsh;
    CDQ(1,N);
    cout<<ans<<endl;
    return 0;
}