首页 > 代码库 > BZOJ4237 稻草人
BZOJ4237 稻草人
4237: 稻草人
Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 835 Solved: 366
[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
0 0
2 2
3 4
4 3
Sample Output
3
思路{
很明显,该题是个偏序问题。
我们考虑怎么利用CDQ分治快速求解。
第一步:按照y排序,分成两段,递归分治。
现在得到两部分,我们要做的就是统计前面区间每个点的对后一个区间点的贡献。
应当要满足x1<x2,y1<y2。但是在这个前一个或后一个区间还是有重复(即被覆盖)。
所以得到第二步:我们考虑用单调队列维护元素的升序降序。
由于一定要查完该点x之前的元素的贡献,所以要把之前的点加入单调队列。
那么有第三步:二分查找最开始的能得到答案的位置,统计答案。
}
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <vector> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define inf (1<<30) #define il inline #define RG register #define LL long long #define maxx 200010 using namespace std; struct point{int x,y;}e[maxx]; int n;int s1[maxx],s2[maxx];LL Ans; bool comp(const point & a,const point & b){return a.y<b.y;} bool Comp(const point & a,const point & b){return a.x<b.x;} il void CDQ(int l,int r){ if(l>=r)return; int mid=(l+r)>>1; sort(e+l,e+r+1,comp);int top1=0,top2=0;CDQ(l,mid),CDQ(mid+1,r); sort(e+l,e+mid+1,Comp),sort(e+mid+1,e+r+1,Comp); for(RG int j=mid+1,i=l;j<=r;++j){ while(top1&&e[s1[top1]].y>=e[j].y)top1--; s1[++top1]=j; while(e[i].x<=e[s1[top1]].x&&i<=mid){ while(top2&&e[s2[top2]].y<e[i].y)top2--; s2[++top2]=i,i++; } int Min=e[s1[top1-1]].x,L=1,R=top2,pos=-1; while(L<=R){ int Mid=(L+R)>>1; if(e[s2[Mid]].x>Min)pos=Mid,R=Mid-1; else L=Mid+1; }if(pos!=-1)Ans+=top2-pos+1; } } il void work(){ scanf("%d",&n);e[0].x=e[0].y=-1; for(RG int i=1;i<=n;++i)scanf("%d%d",&e[i].x,&e[i].y); CDQ(1,n);printf("%lld",Ans);return ; } int main(){ work(); return 0; }
BZOJ4237 稻草人
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。