非常好题目，让我对扫描线思想的理解又一次加深了（虽然本题扫描的不是线，叫扫描点更合适，所以干脆就叫逐点扫描算了）。

题意不多说了，直接点开原题链接即可看。这题求出祭坛最大套多少层有 50 分，在此基础上再算出多少个中心点满足祭坛嵌套层数最大又有 50 分。我们分开来讲。

Subtask 1 : 最大祭坛嵌套层数

首先对于这种二维平面问题，点个数给定 $3\times 10^5$ ，坐标 $10^9$ ，排序+离散化自不必说。然后由于多层嵌套的祭坛需要满足横线端点平行于 x 轴，竖线端点平行于 y 轴，我们可以基于这个特性来考虑怎么解决。

首先我们可以对所有坐标根据 x,y 双关键字排序，按照 x 从小到大，x 相同则 y 从小到大的顺序去遍历。不难得到，如果要求祭坛层数最大，那么祭坛竖线端点最内层的两个端点一定是 x 坐标相同的情况下，y 相邻的（也就是中间没有其他 x 相同的点）。在此基础上只要两者 y 坐标差距大于 1 ，则意味着这里面可以放中心点，就可以查询介于这两个点之间的点为中心（不包括两个端点）时，祭坛最大层数是多少。

设这两个点分别是 $a,b$ （其中 $a$ 比 $b$ 的纵坐标大，两者横坐标一致），那么介于 $a,b$ 点中间的点为中心时（不包括 $a,b$）结果如下：

• 纵向可以嵌套的层数为：横坐标 $x$ 这条线上，在 $a$ 或者其正上方的点个数，以及在 $b$ 或其正下方的点个数，两者取最小值。
• 横向可以嵌套的层数为：对于满足 $x_a=x_b=x,y_a<y<y_b$ 的这些点，计算在其正左方的点个数和在其正右方点个数的较小者。对于所有点的结果取最大值。
• 横向和纵向的结果取最小值即为备选答案。

分析到这里我们就已经知道要怎么维护了。

对于每个点，实时维护：

• 信息 1： $y$ 比当前点大或者小（在其上或下方），$x$ 为特定值的点有多少个
• 信息 2： $x$ 比当前点大或者小（在其左或右方），$y$ 为特定值的点有多少个

这个东西单次维护显然是 $O(1)$ 的，因为我们已经规定了合适的扫描顺序。

然后纵向嵌套就可以直接用信息 1 来 $O(1)$ 求解了。横向嵌套则需要维护纵坐标区间上每个点的信息 2 较小者的最大值，显然用单点赋值区间求 $\max$ 的线段树即可。

然后注意扫描的过程中判断同 x 坐标的相邻两点是否合法，以及在求个数时可能会出现加 1 或者减 1 的偏移，都是不太难的细节。

Subtask 2 : 满足最大祭坛嵌套层数的中心点个数

其实第二个也不难，核心扫描思想和 Subtask 1 是一致的。我们需要判断每个点的纵向嵌套和横向嵌套个数是否均不小于最大层数即可。如果每个点纵向嵌套满足的话，查询纵轴区间内横向嵌套满足的点个数即可。而横向嵌套就是把上面维护“信息 2 较小者的最大值”改为“满足信息 2 较小者大于等于嵌套数”的个数即可。那么就用树状数组维护即可。扫描的思想和 Subtask 1 完全一致。注意树状数组不能无脑单点加，而是单点赋值修改。所以每次加点时需要减去上一次赋值。

总时间复杂度为 $O(n\log n)$ 。

const int N = 300010;
std::pair<int, int> pt[N];
int n, q, xcnt, ycnt;
int ans1, ans2;
int X[N], Y[N];
int U[N], R[N]; // counter at up/right side, which x/y coord = i
int D[N], L[N]; // counter at down/left side, which x/y coord = i
inline void add_ur(int i) { ++U[pt[i].first], ++R[pt[i].second]; }
inline void sub_ur(int i) { --U[pt[i].first], --R[pt[i].second]; }
inline void add_dl(int i) { ++D[pt[i].first], ++L[pt[i].second]; }
inline void sub_dl(int i) { --D[pt[i].first], --L[pt[i].second]; }
// seg for y 
namespace seg
{
    inline int lc(int u) { return u << 1; }
    inline int rc(int u) { return (u << 1) | 1; }
    int val[N << 2];
    inline void pushup(int u) { val[u] = std::max(val[lc(u)], val[rc(u)]); }
    inline void modify(int u, int p, int L, int R, int v)
    {
        if (L == R) return (void)(val[u] = v);
        int M = (L + R) >> 1;
        (p <= M) ? modify(lc(u), p, L, M, v) : modify(rc(u), p, M + 1, R, v);
        pushup(u);
    }
    inline int query(int u, int l, int r, int L, int R)
    {
        if (L > r || R < l || l > r) return 0;
        if (l <= L && R <= r) return val[u];
        int M = (L + R) >> 1;
        return std::max(query(lc(u), l, r, L, M), query(rc(u), l, r, M + 1, R));
    }
}
int lst[N];
namespace bit
{
    inline int lb(int x) { return x & (-x); }
    int a[N];
    inline void add(int pos, int v) { for (int p = pos; p <= ycnt; p += lb(p)) a[p] += v; }
    inline int query(int pos)
    {
        int ret = 0;
        for (int p = pos; p; p -= lb(p)) ret += a[p];
        return ret;
    }
    inline int query(int l, int r) { return (l > r) ? 0 : query(r) - query(l - 1); }
}
int main()
{
    n = rd(), q = rd();
    for (int i = 1; i <= n; ++i)
    {
        pt[i].first = X[i] = rd();
        pt[i].second = Y[i] = rd();
    }
    std::sort(X + 1, X + n + 1), std::sort(Y + 1, Y + n + 1);
    xcnt = std::unique(X + 1, X + n + 1) - X - 1, ycnt = std::unique(Y, Y + n + 1) - Y - 1;
    for (int i = 1; i <= n; ++i)
    {
        pt[i].first = std::lower_bound(X + 1, X + xcnt + 1, pt[i].first) - X;
        pt[i].second = std::lower_bound(Y + 1, Y + ycnt + 1, pt[i].second) - Y;
    }
    std::sort(pt + 1, pt + n + 1);
    // solve subtask 1
    for (int i = 1; i <= n; ++i) add_ur(i);
    for (int i = 1; i <= n; ++i)
    {
        sub_ur(i), add_dl(i);
        seg::modify(1, pt[i].second, 1, ycnt, std::min(L[pt[i].second], R[pt[i].second]));
        // possible to make alter
        if (i > 1 && (pt[i].first == pt[i - 1].first) && (Y[pt[i].second] - Y[pt[i - 1].second] > 1))
        {
            int ans_x = std::min(U[pt[i].first] + 1, D[pt[i].first] - 1);
            int ans_y = seg::query(1, pt[i - 1].second + 1, pt[i].second - 1, 1, ycnt);
            ans1 = std::max(ans1, std::min(ans_x, ans_y));
        }
    }
    if (q == 1) wr(ans1), exit(0); 
    for (int i = 1; i <= n; ++i) sub_dl(i), add_ur(i);
    for (int i = 1; i <= n; ++i)
    {
        sub_ur(i), add_dl(i);
        int flag_y = std::min(L[pt[i].second], R[pt[i].second]) >= ans1;
        bit::add(pt[i].second, flag_y - lst[pt[i].second]), lst[pt[i].second] = flag_y;
        if (i > 1 && (pt[i].first == pt[i - 1].first) && (Y[pt[i].second] - Y[pt[i - 1].second] > 1))
        {
            int flag_x = std::min(U[pt[i].first] + 1, D[pt[i].first] - 1) >= ans1;
            if (flag_x) ans2 += bit::query(pt[i - 1].second + 1, pt[i].second - 1);
        }
    }
    wr(ans2);
}