首页 > 代码库 > bzoj4237 稻草人
bzoj4237 稻草人
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
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$分治。
感觉做法很神奇，自己根本就想不到啊。。
我们考虑如何使用分治计算答案，按照$y$坐标分治，对于上半部分和下半部分分别按照$x$坐标排序。我们枚举上半区间的每个点作为右上角的点来统计答案。
考虑一下上半区间一定能堵住当前点的点，一定是它之前被处理的点中$y$坐标比它小且$x$坐标最大的点，那么这个点我们可以用单调栈求出，所以对于上半区间，我们维护一个$y$坐标递增的单调栈。同样，对于下半区间，我们考虑怎样的点可以被计入答案，在当前点加入以后，那么$x$坐标和$y$坐标都比它小的点绝对不可能被计入答案，于是我们对下半区间维护一个$y$坐标单调递减的单调栈。同时我们在单调栈内二分，只有当下半区间中的点的$x$坐标大于上半区间单调栈中倒数第二个点的$x$坐标，这个点才是对于上半区间当前点合法的答案。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define inf (1<<30)14 #define N (500010)15 #define il inline16 #define RG register17 #define ll long long18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)19 20 using namespace std;21 22 struct data{ int x,y; }q[N],qu[N];23 24 int st1[N],st2[N],hsh[N],n,tot;25 ll ans;26 27 il int gi(){28 RG int x=0,q=1; RG char ch=getchar();29 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();30 if (ch==‘-‘) q=-1,ch=getchar();31 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();32 return q*x;33 }34 35 il int cmpx(const data &a,const data &b){ return a.x<b.x; }36 37 il int cmpy(const data &a,const data &b){ return a.y<b.y; }38 39 il void solve(RG int l,RG int r){40 if (l==r) return; RG int mid=(l+r)>>1,t1=l-1,t2=mid;41 for (RG int i=l;i<=r;++i) if (q[i].y<=mid) qu[++t1]=q[i]; else qu[++t2]=q[i];42 for (RG int i=l;i<=r;++i) q[i]=qu[i]; RG int top1=0,top2=0,L,R,Mid,res;43 for (RG int i=mid+1,j=l;i<=r;++i){44 while (top1 && q[st1[top1]].y>=q[i].y) --top1; st1[++top1]=i;45 for (;j<=mid && q[j].x<q[i].x;++j){46 while (top2 && q[st2[top2]].y<=q[j].y) --top2; st2[++top2]=j;47 }48 L=1,R=top2,res=top2+1;49 while (L<=R){50 Mid=(L+R)>>1;51 if (q[st2[Mid]].x>=q[st1[top1-1]].x) res=Mid,R=Mid-1;52 else L=Mid+1;53 }54 ans+=top2-res+1;55 }56 solve(l,mid),solve(mid+1,r); return;57 }58 59 il void work(){60 n=gi(),q[0].x=q[0].y=-1;61 for (RG int i=1;i<=n;++i) q[i].x=gi(),q[i].y=gi(),hsh[++tot]=q[i].y;62 sort(hsh+1,hsh+tot+1),tot=unique(hsh+1,hsh+tot+1)-hsh-1;63 for (RG int i=1;i<=n;++i) q[i].y=lower_bound(hsh+1,hsh+tot+1,q[i].y)-hsh;64 sort(q+1,q+n+1,cmpx),solve(1,n),printf("%lld\n",ans); return;65 }66 67 int main(){68 File("scarecrow");69 work();70 return 0;71 }
bzoj4237 稻草人
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。