bzoj 4237: 稻草人(CDQ分治+单调栈+二分)
程序员文章站
2022-06-29 21:56:21
...
4237: 稻草人
Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 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]过程如下图
①区间[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
*/