题解：P14426 [JOISC 2014] 稻草人 / Scarecrows

· · 题解

鲜花：为什么想到分治写不出来？？？是不是根本就不会？？？

给出平面上 n 个关键点，求使得左下角和右上角为关键点，且矩形内部不存在其他关键点（不包括边界）的矩形个数。

保证横纵坐标互不相同，n\le2\times 10^5。

固定左下角的点 (x_1,y_1)，考虑什么样的点可以与其配对。假设 (x_2,y_2) 与其配对。那么一定不存在点 (a,b) 使得 a\in(x_1,x_2),b\in(y_1,y_2)。即不存在在这个范围内被 (x_2,y_2) 二维偏序的点，转化一下，如果按照横坐标排序，那么 y_2 就是横坐标限定在 x>x_1，纵坐标限制在 y>y_1 的关于纵坐标的 前缀最小值。

直接枚举复杂度甚至不如 \mathcal O(n^2) 的朴素暴力，点对问题通常可以用分治解决，考虑分治。由于没有横纵坐标都可以任选，于是随便取一维，这里就取横坐标。考虑左侧点怎么样才可以与右侧点匹配。

设在左侧点为 P，右侧可以与 P 匹配的点为 Q，中线横坐标为 m。根据前面的限制，Q 必然是横坐标从 P_x 起，所有 y>y_P 的前缀最小值。然而倘若引入左侧点，难以维护这个前缀最小值。于是考虑转化，这就相当于对于 P_x\sim m 中的最小的比 y_P 大的点 U，使得 y_Q 为从 m 起的前缀最小值且 y_Q<y_U。也就是说，左侧点 P 要统计纵坐标在 (y_P,y_U) 之间所有为前缀最小值的右侧点。

考虑对纵坐标扫描线，这样我们就能实时维护对纵坐标有限制的前缀最小值。维护一个单调栈。 由于我们是对纵坐标做的扫描线，因此已经天然满足纵坐标递减的性质。假设栈为 S，新增点为 (a,b)，只要当栈顶 S_{top} 的横坐标大于 a，一直弹出。在维护单调栈的同时用树状数组统计值，对于左侧的点的维护也是类似。

复杂度为 \mathcal O(n\log^2 n)。

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

const int N = 5e5 + 10;

struct point {
    int x, y;
    int id;
};

struct BIT {
    int n;
    vector <int> t;
    void init (int x) { n = x + 5; t.assign (n + 5, 0); }
    void add (int x, int k) { x ++; for (; x <= n; x += x & -x) t[x] += k; }
    int qry (int x) { x ++; int ret = 0; for (; x; x -= x & -x) ret += t[x]; return ret; }
    int qry (int l, int r) { if (l > r) return 0; return qry (r) - qry (l - 1); }
} bit;

int n;
point p[N];
vector <int> X, Y;
ll ans;

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

    sort (p + l, p + mid + 1, [&](auto x, auto y) { return x.y > y.y; });
    sort (p + mid + 1, p + r + 1, [&](auto x, auto y) { return x.y > y.y; });
    vector <int> s, s2;

    auto out = [&]() {
        bit.add (p[s.back ()].y, -1);
        s.pop_back ();
    };
    auto in = [&](int x) {
        bit.add (p[x].y, 1);
        s.push_back (x);
    };

    int j = mid + 1;
    for (int i = l; i <= mid; i ++) {
        while (j <= r && p[j].y > p[i].y) {
            while (!s.empty () && p[s.back ()].x > p[j].x) out ();
            in (j ++);
        }
        while (!s2.empty () && p[s2.back ()].x < p[i].x) s2.pop_back ();
        int up = s2.empty () ? n : p[s2.back ()].y;
        ans += bit.qry (p[i].y, up);
        s2.push_back (i);
    }

    while (s.size ()) out ();

    sort (p + l, p + r + 1, [&](auto x, auto y) { return x.x < y.x; });
    divide (l, mid);
    divide (mid + 1, r);
} 

int main (void) {

    scanf ("%d", &n); bit.init (n);
    for (int i = 1; i <= n; i ++) scanf ("%d%d", &p[i].x, &p[ p[i].id = i ].y), X.push_back (p[i].x), Y.push_back (p[i].y);
    sort (X.begin (), X.end ()); sort (Y.begin (), Y.end ());
    for (int i = 1; i <= n; i ++) 
        p[i].x = lower_bound (X.begin (), X.end (), p[i].x) - X.begin () + 1,
        p[i].y = lower_bound (Y.begin (), Y.end (), p[i].y) - Y.begin () + 1;
    sort (p + 1, p + n + 1, [&](auto x, auto y) { return x.x < y.x; });

    divide (1, n);

    printf ("%lld\n", ans);

    return 0;
}