[BZOJ4237]稻草人 - A-Failure的博客

题目

Description

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

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

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

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

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

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

Input

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

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

Output

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

Sample Input

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$分治，考虑$CDQ$分治怎么统计左右之间的答案

对于左边的某个点$(x,y)$来说，横坐标大于它的左边的点纵坐标第一个大于它的为$y’$，则它能贡献的答案就是区间右区间中纵坐标在$[y,y’]$之间的点，并且纵坐标必须单调递减

左右区间分别按纵坐标从大到小排序，枚举左区间，左区间中每个点对应着右区间的一个前缀，可以用单调栈维护纵坐标大于$y$且单调递减的点，对于左区间的点，也可以用单调栈维护找到纵坐标第一个大于它的点，然后在右区间的单调栈上二分即可

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=2e5+5;
struct p{
	int x,y;
	bool operator< (const p &a)
	const{
		return x<a.x;
	}
}A[MAX];
int n,Top,_Top;
LL ans;
int st[MAX],_st[MAX],_id[MAX],id[MAX];
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
int look(int x)
{
	int l=1,r=Top,ans=Top+1;
	while(l<=r)
	{
		if(A[st[mid]].y<x) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
void Solve(int l=1,int r=n)
{
	if(l==r) return;
	Solve(l,mid),Solve(mid+1,r),Top=_Top=0;
	for(int i=l,L=mid+1;i<=mid;++i)
	  {
	  	for(;L<=r&&A[id[L]].y>A[id[i]].y;++L)
	  	  {
	  	  	while(Top&&A[id[L]].x<A[st[Top]].x) --Top;
	  	  	st[++Top]=id[L];
		  }
		while(_Top&&A[id[i]].x>A[_st[_Top]].x) --_Top;
		if(!_Top) ans+=Top;
		else ans+=Top-look(A[_st[_Top]].y)+1;
		_st[++_Top]=id[i];
	  }
	for(int i=l,L=l,R=mid+1;i<=r;++i)
	  if((R>r||A[id[L]].y>A[id[R]].y)&&L<=mid) _id[i]=id[L++];
	  else if((L>mid||A[id[R]].y>A[id[L]].y)&&R<=r) _id[i]=id[R++];
	for(int i=l;i<=r;++i)
	  id[i]=_id[i];
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	  A[i].x=read(),A[i].y=read(),id[i]=i;
	sort(A+1,A+1+n);
	return Solve(),printf("%lld\n",ans),0;
}

题目