【BZOJ4237】稻草人

题意

给定平面上 \(N\) 个关键点，询问有多少个矩形满足左下和右上各有一个关键点，且矩形中间没有关键点。

\(N\le 2\cdot 10^5\) .

题解

我们按 \(x\) 排序分治，对于左右两边的区间按 \(y\) 排序。

考虑左边的点对右边的每个点产生的贡献。

比较容易发现，产生贡献的点的 \(x\) 一定单减，我们维护一个单调栈。

我们注意到，如果左边的点能和之前统计的右边的点形成矩形，那么这个点一定不会对当前点产生贡献。

那么做法就比较显然了：我们对于离当前点最近的横坐标比它小的点，在左边二分找纵坐标比该点小的点数，统计答案时减掉这部分点即可。

怎么找这样的点？我们对右边维护一个横坐标单增的单调栈即可。

时间复杂度 \(O(n\log ^2 n)\) ，代码非常好写。

#include<cstdio>

#include<algorithm>

using namespace std;

inline int gi()

{

	char c; int x=0;

	for(;c<'0'||c>'9';c=getchar());

	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';

	return x;

}

const int N=200005;

struct node {

	int x,y;

} a[N],b[N];

bool operator < (node s, node t) {

	return s.x<t.x;

}

bool cmp(node s, node t) {

	return s.y<t.y;

}

int n,s1[N],s2[N];

long long ans;

int _bound(int w, int r)

{

	int l=1;

	while(l<=r)

	{

		int mid=l+r>>1;

		a[s2[mid]].y<w?l=mid+1:r=mid-1;

	}

	return l-1;

}

void cdq(int l, int r)

{

	if(l==r) return ;

	int mid=l+r>>1;

	cdq(l,mid),cdq(mid+1,r);

	int t1=0,t2=0;

	for(int i=mid+1,j=l;i<=r;++i)

	{

		for(;t1&&a[s1[t1]].x>a[i].x;--t1);

		s1[++t1]=i;

		for(;j<=mid&&a[j].y<a[i].y;++j)

		{

			for(;t2&&a[s2[t2]].x<a[j].x;--t2);

			s2[++t2]=j;

		}

		ans+=t2-_bound(a[s1[t1-1]].y,t2);

	}

	merge(a+l,a+mid+1,a+mid+1,a+r+1,b,cmp);

	for(int i=l,j=0;i<=r;++i,++j) a[i]=b[j];

}

int main()

{

	n=gi();

	for(int i=1;i<=n;++i) a[i].x=gi(),a[i].y=gi();

	sort(a+1,a+1+n);

	cdq(1,n);

	printf("%lld",ans);

}

巴特西

【BZOJ4237】稻草人

题意

题解

最新文章

热门文章