[BZOJ4237]稻草人(CDQ分治,单调队列)

发布于 2018-03-26  96 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4237]稻草人(CDQ分治,单调队列)

Description

JOI村有一片荒地,上面竖着N个稻草人,村民们每年多次在稻草人们的周围举行祭典。
有一次,JOI村的村长听到了稻草人们的启示,计划在荒地中开垦一片田地。和启示中的一样,田地需要满足以下条件:
田地的形状是边平行于坐标轴的长方形;
左下角和右上角各有一个稻草人;
田地的内部(不包括边界)没有稻草人。
给出每个稻草人的坐标,请你求出有多少遵从启示的田地的个数

Tag

CDQ分治,单调队列

解决思路

排序后对横坐标,整体二分,考虑跨越当前分治中心的贡献。
其实只要考虑点怎么放会导致遮住一些点。我们发现,若按照y坐标从大到小考虑贡献,我们需要对左边部分维护一个y坐标从大到小,x坐标从大到小的单调队列;对右边维护一个y从大到小,x从小到大的单调队列。
每一次在左边加入一个点(x0,y0),会弹出左边之前的若干个点,然后把右边y坐标大于y0的点加入单调队列,同样要保证单调性,然后在右边的单调队列中二分y坐标就可以得到这一次左边这个点与右边的组合得到的贡献了,二分的值域区间是当前枚举到的左点(x0,y0)的y0,到左单调队列的前一个元素的纵坐标。
算完这一次的贡献后,回归到上一层分治之前,因为要方便上一层按照y坐标从大到小加入,所以按y坐标归并排序。
需要注意二分的两端极限情况,这里采用的是临时设一个值和边界判断的方式,防止越界。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=200010;
const int inf=2147483647;

class Pos
{
public:
    int x,y;
};

int n;
ll Ans;
Pos P[maxN],Backup[maxN];
int Queue1[maxN],Queue2[maxN];

bool cmp(Pos A,Pos B);
void Solve(int l,int r);

int main()
{
    ios::sync_with_stdio(false);

    cin>>n;
    for (int i=1;i<=n;i++) cin>>P[i].x>>P[i].y;
    sort(&P[1],&P[n+1],cmp);

    Solve(1,n);

    cout<<Ans<<endl;
    return 0;
}

bool cmp(Pos A,Pos B)
{
    if (A.x!=B.x) return A.x<B.x;
    return A.y<B.y;
}

void Solve(int L,int R)
{
    if (L==R) return;
    int mid=(L+R)>>1;
    Solve(L,mid);Solve(mid+1,R);

    int h1=0,h2=0;
    int nowans=0;
    for (int i=L,j=mid+1;i<=mid;i++)
    {
        //弹出左单调队列不合法节点,保证单调性
        while ((h1!=0)&&(P[Queue1[h1]].x<P[i].x)) h1--;
        Queue1[++h1]=i;//把当前节点加入
        while ((j<=R)&&(P[j].y>P[i].y))//把右部分纵坐标大于当前左部分枚举到的点的纵坐标的加入右边的单调队列,因为这时它可能有贡献了
        {
            while ((h2!=0)&&(P[Queue2[h2]].x>P[j].x)) h2--;//注意也要保证单调性
            Queue2[++h2]=j;j++;
        }
        if (h2==0) continue;//当第二个队列为空的时候,一定没有贡献
        int p1,p2;//p1记录第一个一个小于当前y的位置,p2记录第一个小于等于左单调队列中前一个的y的位置,注意y是单调降的
        int l=0,r=h2;
        P[0].y=inf;
        while (l<=r)
        {
            int mid=(l+r)>>1;
            if (P[Queue2[mid]].y>P[i].y){
                p1=mid;l=mid+1;
            }
            else r=mid-1;
        }
        if (h1==1) p2=1;//特判左单调队列长度为1,此时不存在前一个,所以直接是最大的
        else
        {
            l=1,r=h2+1;P[0].y=0;Queue2[h2+1]=0;P[0].x=-10;
            while (l<=r)
            {
                int mid=(l+r)>>1;
                if (P[Queue2[mid]].y<=P[Queue1[h1-1]].y){
                    p2=mid;r=mid-1;
                }
                else l=mid+1;
            }
        }
        if (p1>=p2) nowans+=(p1-p2+1),Ans+=(p1-p2+1);//统计答案
    }
    int p1=L,p2=mid+1;//按照y归并排序,方便上一层处理
    for (int i=L;i<=R;i++)
        if ((p1<=mid)&&((p2>R)||(P[p1].y>P[p2].y)))
            Backup[i]=P[p1++];
        else Backup[i]=P[p2++];
    for (int i=L;i<=R;i++) P[i]=Backup[i];
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4237]稻草人(CDQ分治,单调队列)


HNCJ OIer