JOI村有一片荒地，上面竖着N个稻草人，村民们每年多次在稻草人们的周围举行祭典。
有一次，JOI村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件：
田地的形状是边平行于坐标轴的长方形；
左下角和右上角各有一个稻草人；
田地的内部(不包括边界)没有稻草人。
给出每个稻草人的坐标，请你求出有多少遵从启示的田地的个数
JOI 2013~2014 春季training合宿 竞技3 By PoPoQQQ
晚上看ysq大佬(%%%)秒切NeighThorn做过的题的时候听到玉环在思考这题...然后NeighThorn和YouSiki果断弃掉NT做过的水题来思考YYH大佬的神题...
然后两个人对着屏幕和草稿纸陷入了深思...
一千八百万年之后NT赶脚自己YY出了一个漏洞百出的方法...(真的是漏洞百出...
感觉我们可以统计每个点对答案的贡献，因为这是个二维的东西，所以可能可以通过分治什么的降到一维...
我们把所有的点按照x轴坐标排序，然后对y坐标分治，这样我们统计对于上层的每个节点下层有多少个节点可以和其构成合法答案...
如果下层的点出现了这种情况...显然对于3节点来说1节点是没有用的...
所以我们对于下层节点维护一个y坐标单调递减的栈，对于上层的每个节点在下层的单调栈里二分答案...
然后被YouSiki大佬D得很惨...虽然他也被NT卡掉了(hia~hia~hia~...
然后NT满心欢喜地对YouSiki说：“你去写吧，我懒得写了..."被YouSiki严肃地拒绝了...
对于一切早已习惯并且淡然了的NT回到电脑屏幕前开始发呆，忽然发现这样是错误的，然后错的还很明显...(所以NT和YouSiki的脑子都锈掉了？？？
于是NT和YouSiki再次经过了和平的争吵之后YouSiki童鞋说出了正解...
我们现在不对上层的每个节点去寻找答案，而是直接计算跨越上下层的合法矩形个数...
我们对于上层节点维护y坐标单调递增的栈，下层节点维护y坐标单调递减的栈...下层为什么单调递减上面已经说过了...
上层单调递增是因为如果存在这样的情况，3节点和2节点组成的矩形是合法的，2节点和4节点的矩形也是合法的...
一个分治里面有个二分...时间复杂度$O(nlog^{2}n)$...
然后NT表示YouSiki太厉害了...然后大爷就又愉快地开始了每天必做功课：催人...
稍后再放...
原文：http://www.cnblogs.com/neighthorn/p/6412068.html