题面
$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;
}