BZOJ4237【JOI2013】稻草人 < CDQ分治+单调栈 >

Problem

【JOI2013】稻草人

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

$\mathrm{JOI}$村有一片荒地，上面竖着$N$个稻草人，村民们每年多次在稻草人们的周围举行祭典。
有一次，$\mathrm{JOI}$村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件：

• 田地的形状是边平行于坐标轴的长方形
• 左下角和右上角各有一个稻草人
• 田地的内部（不包括边界）没有稻草人

给出每个稻草人的坐标，请你求出有多少遵从启示的田地的个数。

Input

第一行一个正整数$N$，代表稻草人的个数。
接下来$N$行，第$i$行$(1\le i\le N)$包含$2$个由空格分隔的整数$X_i$和$Y_i$，表示第$i$个稻草人的坐标。

Output

输出一行一个正整数，代表遵从启示的田地的个数。

Sample Input

4
0 0
2 2
3 4
4 3

Sample Output

3

HINT

所有满足要求的田地由下图所示：


$1\le N\le 2\times 10^5$
$0\le X_i\le 10^9(1\le i\le N)$
$0\le Y_i\le 10^9(1\le i\le N)$
$X_i(1\le i\le N)$互不相同。
$Y_i(1\le i\le N)$互不相同。

标签：CDQ分治 单调栈

Solution

暑假听$\mathrm{ZCY}$讲过这道题，当时用的是线段树上维护单调栈。
发现$\mathrm{CDQ}$分治也可以用相同复杂度过掉此题，而且还更好写。

首先$\mathrm{CDQ}$分治降维，把两维降成一维，即把$y$的限制去掉。
先离散化，再按$x$值排序，随后开始分治。
对于每次分治，把区间分为两个部分$[l,mid]$和$[mid+1,r]$，把$y$值在两个区间内的分开。然后逐个加入$y$值大于$mid$的点，并维护单调栈，再把所有$x$值小于它且$y$值小于等于$mid$的点加入另一个单调栈，再单调栈上二分找到分界点，统计以此点作为右上角可组成的方形个数。

Code

#include <bits/stdc++.h>
#define MAX_N 200000
#define lb lower_bound
using namespace std;
typedef long long lnt;
int n, mp[2][MAX_N+5];    lnt ans;
struct node {int x, y;} p[MAX_N+5], q[MAX_N+5], sta[2][MAX_N+5];
bool cmp(const node &a, const node &b) {return a.x < b.x;}
void solve(int l, int r) {
    if (l == r)	return;	int mid = l+r>>1;
    int m0 = l, m1 = mid+1, tp0 = 0, tp1 = 0;
    for (int i = l; i <= r; i++)
        if (p[i].y <= mid)	q[m0++] = p[i];
        else	q[m1++] = p[i];
    memcpy(p+l, q+l, sizeof(node)*(r-l+1));
    for (int p0 = l, p1 = mid+1; p1 <= r; ) {
        while (p0 <= mid && p[p0].x < p[p1].x) {
            while (tp0 && sta[0][tp0].y < p[p0].y)	tp0--;
            sta[0][++tp0] = p[p0], p0++;
        }
        while (tp1 && sta[1][tp1].y > p[p1].y)	tp1--;
        sta[1][++tp1] = p[p1], p1++;
        ans += tp0-(lb(sta[0]+1, sta[0]+tp0+1, sta[1][tp1-1], cmp)-sta[0])+1;
    }
    solve(l, mid), solve(mid+1, r);
}
int main() {
    scanf("%d", &n);	for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y), mp[0][i-1] = p[i].x, mp[1][i-1] = p[i].y;
    sort(mp[0], mp[0]+n), sort(mp[1], mp[1]+n);	int m0 = unique(mp[0], mp[0]+n)-mp[0], m1 = unique(mp[1], mp[1]+n)-mp[1];
    for (int i = 1; i <= n; i++)	p[i].x = lb(mp[0], mp[0]+m0, p[i].x)-mp[0]+1, p[i].y = lb(mp[1], mp[1]+m1, p[i].y)-mp[1]+1;
    sort(p+1, p+n+1, cmp), solve(1, n);	return printf("%lld", ans), 0;
}