题目链接：传送门

Description

懒得放，太长了 大概意思就是让你在平面内找一点，使得它的四个正方向上的点的数量的最小值最大

Hint

N(点数) <= 1e6 0 <= x, y <= N

Sample Input

26 0 5 1 1 1 5 1 9 3 5 3 10 4 0 4 1 4 2 4 4 4 6 4 9 4 11 5 0 5 2 5 4 5 8 5 9 5 10 5 11 6 5 7 5 8 5 9 10 10 2 10 5

Sample Ouput

3 2

Solution

这道题的做法比较巧妙 首先二分一个答案，然后用扫描线的思想维护两个数组up[i], down[i]表示第i列的上方有多少点，下方有多少点， 那么满足题意的点一定满足up[i] >= t, down[i] >= t(t为二分的答案)，这是竖列的要求。 然后对于横行的要求的话，我们找到可行的左端点和右端点， 在这个区间内用树状数组维护一下满足数列要求的点，查询一个区间和即可 (我知道没讲清，反正自己懂就好了。。。)

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
#define lowbit(x) x & (-x)

using namespace std;

const int Maxn = 100000 + 100;

int N, M;
int Cnt[Maxn];
int up[Maxn], down[Maxn];
int Sum[Maxn * 2];
int l[Maxn], r[Maxn];
int a[Maxn], b[Maxn];
int Val[Maxn];

vector <int> vec[Maxn];

inline void add (int x, int v)
{
    while (x <= N)
    {
        Sum[x] += v;
        x += lowbit(x);
    }
}

inline int Query (int x)
{
    int Ans = 0;
    while (x)
    {
        Ans += Sum[x];
        x -= lowbit(x);
    }
    return Ans;
}

inline void Update(int x, int y)
{
    if (Val[x] == y) return ;
    if (y == 1) add(x, 1);
    else add(x, -1);
    Val[x] = y;
}


inline int Check (int t)
{
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(Sum, 0, sizeof(Sum));
    memset(Val, 0, sizeof(Val));
    for (int i = 1; i <= N; ++i) up[i] = 0, down[i] = Cnt[i];
    for (int i = 1; i <= N; ++i)
        if (vec[i].size() >= 2 * t)
            l[i] = vec[i][t - 1] + 1, r[i] = vec[i][vec[i].size() - t] - 1;
        else l[i] = N + 1, r[i] = 0;
    int sum = 0;
    for (int i = 1; i <= N; ++i)
    {
        vector <int> Vis;
        for (int j = 0; j < vec[i - 1].size(); ++j)
        {
            int y = vec[i - 1][j];
            Vis.push_back(y);
            up[y] ++;
            if (up[y] >= t) a[y] = 1; else a[y] = 0;
        }

        for (int j = 0; j < vec[i].size(); ++j)
        {
            int y = vec[i][j];
            Vis.push_back(y);
            down[y] --;
            if (down[y] >= t) b[y] = 1; else b[y] = 0;
        }

        for (int j = 0; j < Vis.size(); ++j)
        {
            int y = Vis[j];
            Update(y, a[y] + b[y] == 2);
        }

        if (l[i] <= r[i])
            sum += Query(r[i]) - Query(l[i] - 1);
    }
    return sum;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif

    scanf("%d", &M);
    N = M + 1;
    for (int i = 1; i <= M; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ++x, ++y;
        vec[x].push_back(y);
        Cnt[y] ++;
    }

    for (int i = 1; i <= N; ++i) sort(vec[i].begin(), vec[i].end());

    int l = 0, r = M, Ans = -1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (Check(mid)) l = mid + 1, Ans = mid;
        else r = mid - 1;
    }

    cout<<Ans<<endl<<Check(Ans)<<endl;
    return 0;
}