Description

JOI 村有一片荒地, 上面竖着 \(n\) 个稻草人, 村民们每年多次在稻草人们的周围举行祭典.

有一次, JOI 村的村长听到了稻草人们的启示, 计划在荒地中开垦一片田地. 和启示中的一样, 田地需要满足以下条件:

  1. 田地的形状是边平行于坐标轴的长方形;
  2. 左下角和右上角各有一个稻草人;
  3. 田地的内部 (不包括边界) 没有稻草人.

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

Input

第一行一个正整数 \(n\), 代表稻草人的个数;

接下来 \(n\) 行, 第 \(i\) 行 \((1 \leq i \leq n)\) 包含 \(2\) 个由空格分隔的整数 \(x_i, y_i\), 表示第 \(i\) 个稻草人的坐标.

Output

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

Sample Input

4
0 0
2 2
3 4
4 3

Sample Output

3

Data Range

对于所有数据, 满足:\(1 \leq n \leq 2 \times 10^5, 0 \leq x_i, y_i \leq 10^9\), 且 \(x_i\) 互不相同,\(y_i\) 互不相同.

Explanation

感觉好奇怪, 明明 CDQ 分治就是归并 DP......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 200100;
const int infinit = 0x7fffffff;

struct point {
    int x, y; };
bool cmp_x(point a, point b) {
    return a.x < b.x; }
bool cmp_y(point a, point b) {
    return a.y > b.y; }

int n;
point p[maxn], stk1[maxn], stk2[maxn];

int find(int val, int limit)
{
    int l = 1, r = limit;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (stk1[mid].y <= val)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return r;
}

lli solve(int l, int r)
{
    if (l >= r)
        return 0;
    // Splitting left and right
    int mid = (l + r) / 2;
    lli res = 0;
    // Conquering left part
    res += solve(l, mid);
    // Reasoning with the joining of two sections
    sort(p + l, p + mid + 1, cmp_y);
    sort(p + mid + 1, p + r + 1, cmp_y);
    int top1 = 0, top2 = 0;
    stk1[0].y = stk2[0].y = infinit;
    for (int i = l, j = mid+1; i <= mid; i++) {
        while (j <= r && p[j].y > p[i].y) {
            while (top1 > 0 && p[j].x < stk1[top1].x)
                top1 -= 1; // stk1.pop();
            stk1[++top1] = p[j++]; // stk1.push(p[j++]);
        }
        while (top2 > 0 && p[i].x > stk2[top2].x)
            top2 -= 1; // stk2.pop();
        stk2[++top2] = p[i];
        int l_f = find(stk2[top2-1].y, top1) + 1,
            r_f = find(stk2[top2].y, top1);
        if (l_f <= r_f)
            res += r_f - l_f + 1;
    }
    sort(p + l, p + mid + 1, cmp_x);
    sort(p + mid + 1, p + r + 1, cmp_x);
    // Conquering right part
    res += solve(mid + 1, r);
    // Finalizing output
    return res;
}
int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &p[i].x, &p[i].y);
    sort(p + 1, p + n + 1, cmp_x);
    lli res = solve(1, n);
    printf("%lld\n", res);
    return 0;
}