欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bzoj 4237: 稻草人(CDQ分治+单调栈+二分)

程序员文章站 2022-06-29 21:56:21
...

4237: 稻草人

Time Limit: 40 Sec  Memory Limit: 256 MB
Submit: 1352  Solved: 594
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

4
0 0
2 2
3 4
4 3

Sample Output

3


所有点按y坐标排序之后进行CDQ分治,对于当前区间[L, R]过程如下图

bzoj 4237: 稻草人(CDQ分治+单调栈+二分)

①区间[L, mid]和区间(mid, R]先单独按x从小到大排序,

②对于区间[L, mid]维护一个纵坐标递减的单调栈s1,对于区间(mid, R]维护一个纵坐标递增的单调栈s2

对于栈s2,暴力枚举栈内相邻两个元素,在栈s1中二分出在这两个元素中间的点有多少个并加进答案

如上图,所有红点是当前在栈中的点,假设当前暴力到点a和b,那么就相当于在下面那个绿矩形中找出横坐标在点a和点b中间的点有多少个,结果显而易见为2个(红色矩阵中那两个点),ans += 2


#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
typedef struct Res
{
	int x, y;
	bool operator < (const Res &b) const
	{
		if(y<b.y)
			return 1;
		return 0;
	}
}Res;
Res s[200005], s1[200005], s2[200005];
LL ans;
int p[200005], q[200005];
bool comp(Res a, Res b)
{
	if(a.x<b.x)
		return 1;
	return 0;
}
void CDQ(int l, int r)
{
	int m, i, p, top, t2, L, R, mid;
	if(l==r)
		return;
	m = (l+r)/2;
	CDQ(l, m);
	CDQ(m+1, r);
	sort(s+l, s+m+1, comp);
	sort(s+m+1, s+r+1, comp);
	p = l, top = t2 = 0;
	s2[0].x = -10000;
	for(i=m+1;i<=r;i++)
	{
		while(top>=1 && s1[top].y>s[i].y)
			top--;
		s1[++top] = s[i];
		while(p<=m && s[p].x<s[i].x)
		{
			while(t2>=1 && s2[t2].y<s[p].y)
				t2--;
			s2[++t2] = s[p++];
		}
		L = 0, R = t2;
		while(L<R)
		{
			mid = (L+R)/2;
			if(s2[mid].x<s1[top-1].x)
				L = mid+1;
			else
				R = mid;
		}
		if(s2[R].x<s1[top-1].x)
			R++;
		ans += t2-R+1;
	}
}
int main(void)
{
	int n, i;
	scanf("%d", &n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d", &s[i].x, &s[i].y);
		p[i] = s[i].x;
	}
	sort(p+1, p+n+1);
	for(i=1;i<=n;i++)
		s[i].x = lower_bound(p+1, p+n+1, s[i].x)-p;
	sort(s+1, s+n+1);
	CDQ(1, n);
	printf("%lld\n", ans);
	return 0;
}
/*
6
0 2
2 1
4 0
1 10
3 11
5 12
*/

相关标签: bzoj