BZOJ4237 稻草人

4237: 稻草人

Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 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

Sample Output

思路{

　　很明显，该题是个偏序问题。

　　我们考虑怎么利用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;
}