首页 > 代码库 > BZOJ4237 稻草人
BZOJ4237 稻草人
【问题描述】
JOI村有一片荒地,上面竖着N个稻草人,村民们每年多次在稻草人们的周围举行祭典。
有一次,JOI村的村长听到了稻草人们的启示,计划在荒地中开垦一片田地。和启示中的一样,田地需要满足以下条件:
田地的形状是边平行于坐标轴的长方形;
左下角和右上角各有一个稻草人;
田地的内部(不包括边界)没有稻草人。
给出每个稻草人的坐标,请你求出有多少遵从启示的田地的个数
【输入格式】
第一行一个正整数N,代表稻草人的个数
接下来N行,第i行(1<=i<=N)包含2个由空格分隔的整数Xi和Yi,表示第i个稻草人的坐标
【输出格式】
输出一行一个正整数,代表遵从启示的田地的个数
【输入样例】
4
0 0
2 2
3 4
4 3
【输出样例】
3
【数据范围】
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分治+二分栈
解题报告:思想很简单,直接上代码
#include <iostream> #include <iomanip> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout) #define RG register #define ll long long const int N = 200500; using namespace std; int gi(){char ch=getchar();int x=0; while(ch<‘0‘ || ch>‘9‘)ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();} return x;} int n;ll ans; struct date{int x,y;}f[N],a1[N],a2[N],q1[N],q2[N]; int cmp(date a,date b){return a.x<b.x;} int cop(date a,date b){return a.y<b.y;} int find(int h,int x){ int l=1,r=x,k=0,mid; while(l<=r){ mid=(l+r)>>1; if (q2[mid].y<h) r=mid-1; else l=mid+1,k=mid; } return k; } void cdq(int l,int r){ if (l>=r) return; int mid=(l+r)>>1,b1=0,b2=0,top1=0,top2=0;RG int i,j,t=0; q1[0]=(date){n+1,n+1}; cdq(l,mid); cdq(mid+1,r); for (i=l,j=mid+1; i<=mid; i++){ a1[++b1]=f[i]; while(j<=r && f[j].y>f[i].y){ a2[++b2]=f[j]; while(top2 && f[j].x<q2[top2].x) top2--; q2[++top2]=f[j++]; } while(top1 && f[i].x>q1[top1].x) top1--; q1[++top1]=f[i]; ans+=top2-find(q1[top1-1].y,top2); } while(j<=r) a2[++b2]=f[j++]; i=1,j=1,t=l; while(i<=b1 && j<=b2) if (a1[i].y>a2[j].y) f[t++]=a1[i++]; else f[t++]=a2[j++]; while(i<=b1) f[t++]=a1[i++]; while(j<=b2) f[t++]=a2[j++]; return; } int main(){ File("4237"); RG int i;n=gi(); for (i=1; i<=n; i++) f[i]=(date){gi()+1,gi()+1}; sort(f+1,f+n+1,cop); for (i=1; i<=n; i++) f[i].y=i; sort(f+1,f+n+1,cmp); for (i=1; i<=n; i++) f[i].x=i; cdq(1,n); printf("%lld",ans); return 0; }
BZOJ4237 稻草人
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。