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

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


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

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

Description

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

Tag

CDQ分治,单调队列

解决思路

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

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

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


HNCJ OIer 一枚