[文章目录]
Description
有一次，JOI村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件：
田地的形状是边平行于坐标轴的长方形；
左下角和右上角各有一个稻草人；
田地的内部(不包括边界)没有稻草人。
给出每个稻草人的坐标，请你求出有多少遵从启示的田地的个数，坐标<=10^9，n<=2*10^5
CDQ分治。
按照y坐标分治，分治左右区间后处理当前区间，即跨过左右区间的合法个数。
枚举x，对于右区间的点，处理出每个点左边第一个比其y小的点的x，记为区间左端点，当前点的x为右端点【即没有点在当前点的左下方对应的x的区间】，累加这段x区间对应左区间的答案，即按照x递增维护y递减的单调栈中对应x区间点的个数【即没有一个点的右上方有点的个数】
时间复杂度nlogn
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 201000
typedef long long ll;
ll ans;
int n;
struct node
{
int x,y;
}a[N],z1[N],z2[N];
bool operator < (node x,node y){return x.x<y.x;}
bool cmpx(node x,node y){return x.x==y.x ? x.y>y.y : x.x<y.x;}
bool cmpy(node x,node y){return x.y<y.y;}
void calc(int l,int r)
{
if(a[l].y==a[r].y) return ;
int i,cnt=1,mid;
for(i=l+1;i<=r;++i) cnt+=(a[i].y!=a[i-1].y);
cnt>>=1; cnt--;
for(i=l+1;i<=r;++i)
{
cnt-=(a[i].y!=a[i-1].y);
if(cnt==-1) mid=i-1;
}
calc(l,mid); calc(mid+1,r);
sort(a+l,a+mid+1,cmpx); sort(a+mid+1,a+r+1,cmpx);
int n1=l,n2=mid+1,t1=0,t2=0;
for(i=l;i<=r;++i)
{
if(n1<=mid&&a[n1].x<a[n2].x)
{
while(t1&&z1[t1].y<=a[n1].y) --t1;
z1[++t1]=a[n1]; ++n1;
}
else if(n2<=r)
{
while(t2&&z2[t2].y>=a[n2].y) --t2;
ans+=t1-(lower_bound(z1+1,z1+t1+1,z2[t2])-z1)+1;
z2[++t2]=a[n2]; ++n2;
}
}
}
int main()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmpy);
calc(1,n);
printf("%lld",ans);
return 0;
}