稻草人

Time Limit: 40 Sec Memory Limit: 256 MB

Description

JOI村有一片荒地，上面竖着N个稻草人，村民们每年多次在稻草人们的周围举行祭典。

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

田地的形状是边平行于坐标轴的长方形；

左下角和右上角各有一个稻草人；

田地的内部(不包括边界)没有稻草人。

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

Input

第一行一个正整数N，代表稻草人的个数

接下来N行，第i行(1<=i<=N)包含2个由空格分隔的整数Xi和Yi，表示第i个稻草人的坐标

Output

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

Sample Input

4
　0 0
　2 2
　3 4
　4 3

Sample Output

3

HINT

1<=N<=2*10^5

0<=Xi<=10^9(1<=i<=N), Xi(1<=i<=N)互不相同。

0<=Yi<=10^9(1<=i<=N), Yi(1<=i<=N)互不相同。

Solution

O(n^2)做法很显然，既然这样，我们就使用惯用套路，我们先对 y 进行分治，将上面的点视为右上角的点，下面的视为左下角的点，统计答案。
　　首先把两部分的点分别按照 x 升序排序。
　　然后枚举上面的每个点。
　　显然，约束到它拓展的是 在它左下方最接近的点。
　　同时，下面的点最近的右上方点约束到点的拓展。

那我们对于上面维护一个 y 递增的单调栈，对下面维护一个 y 递减的单调栈。
　　枚举到上面的点的时候，把 x 小于它的下面的点加入下面的那个单调栈，然后二分一下可行的位置就可以了。
　　（显然，只有当下面的x > 上面单调栈倒数第二个点的 x 的时候 才可以被加入答案）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 1000005;

int get()
{
    int res = 1, Q = 1; char c;
    while( (c = getchar()) < 48 || c > 57)
        if(c == '-') Q = -1;
    if(Q) res = c - 48;
    while( (c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res * Q;
}

int n;

struct point
{
    int x, y;
}a[ONE];

bool cmpx(const point &a, const point &b) {return a.x < b.x;}
bool cmpy(const point &a, const point &b) {return a.y < b.y;}

int Stk_down[ONE], Stk_up[ONE];
s64 Ans;

void Solve(int l, int r)
{
    if(l >= r) return;
    int mid = l + r >> 1;

    sort(a + l, a + r + 1, cmpy);
    sort(a + l, a + mid + 1, cmpx);
    sort(a + mid + 1, a + r + 1, cmpx);

    int top_up = 0, top_down = 0;
    int now = l;

    for(int i = mid + 1; i <= r; i++)
    {
        while(top_up > 0 && a[Stk_up[top_up]].y >= a[i].y) top_up--;
        Stk_up[++top_up] = i;

        while(now <= mid && a[now].x <= a[i].x)
        {
            while(top_down > 0 && a[Stk_down[top_down]].y <= a[now].y) top_down--;
            Stk_down[++top_down] = now;
            now++;
        }

        int left = 1, right = top_down, pos = 0;
        int lx = top_up - 1 > 0 ? a[Stk_up[top_up - 1]].x : -1;

        while(left < right - 1)
        {
            int middle = left + right >> 1;
            if(a[Stk_down[middle]].x >= lx)
                right = middle;
            else
                left = middle;
        }


        if(a[Stk_down[left]].x >= lx) pos = left;
        else
            if(a[Stk_down[right]].x >= lx) pos = right;

        if(pos) Ans += top_down - pos + 1;
    }

    Solve(l, mid), Solve(mid + 1, r);
}

int main()
{
    n = get();
    for(int i = 1; i <= n; i++)
        a[i].x = get(), a[i].y = get();

    Solve(1, n);
    printf("%lld", Ans);
}