bzoj 4237: 稻草人 -- CDQ分治

4237: 稻草人

Time Limit: 40 Sec  Memory Limit: 256 MB

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

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)互不相同。

 

 

Source

先将x轴排序，然后CDQ分治，这样先保证左面x值一定小于右面

然后两边分别按y轴排序，然后去找合法解

我们可以左面维护x单调递增的栈，右面维护x单调递减的栈，这样对于左面的每一位在右面二分查找就好

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define inf 1000000007

#define ll long long

#define N 200010

inline int rd()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n;

ll ans;

struct qaz{int x,y;}a[N],b[N];

bool cmp(qaz a,qaz b){return a.x<b.x;}

int q1[N],q2[N];

int fd(int x,int l,int r)

{

    int mid;

    while(l+<r)

    {

        mid=l+r>>;

        if(a[q2[mid]].y<x) l=mid;

        else r=mid;

    }

    return l;

}

void cdq(int l,int r)

{

    if(l==r) return;

    int mid=l+r>>;

    cdq(l,mid);cdq(mid+,r);

    int i,j=l,t1=,t2=;

    for(i=mid+;i<=r;i++)

    {

        while(t1&&a[q1[t1]].x>a[i].x) t1--;

        q1[++t1]=i;

        for(;j<=mid&&a[j].y<a[i].y;j++)

        {

            while(t2&&a[q2[t2]].x<a[j].x) t2--;

            q2[++t2]=j;

        }

        ans+=t2-fd(a[q1[t1-]].y,,t2+);

    }

    for(i=l,t1=l,t2=mid+;i<=r;i++) b[i]=((t1<=mid&&a[t1].y<a[t2].y)||t2>r)?a[t1++]:a[t2++];

    for(i=l;i<=r;i++) a[i]=b[i];

}

int main()

{

    n=rd();

    for(int i=;i<=n;i++) a[i].x=rd(),a[i].y=rd();

    sort(a+,a+n+,cmp);

    cdq(,n);

    printf("%lld\n",ans);

    return ;

}