Friendly Points

题目描述

Consider $n$ distinct points on a plane. Two points from that set are said to be friends, when there exists a rectangle with sides parallel to coordinate axes that contains those two points and doesn’t contain any other point from the given set. A rectangle is said to contain a point if the point lies within the rectangle or on its border. How many pairs of friends are there among the given points?

题意概述

给定平面上的$n$个点。定义一对点是友好点对当且仅当存在一个各边平行于坐标轴的矩形仅包含这两个点。一个点被一个矩形包含当且仅当该点在矩形内部或边界上。求有多少对友好点对。

数据范围：$1 \le n \le 10^5$。

算法分析

用 CDQ 分治，把平面上的问题转化为序列上的问题。将点分成上下两个部分，考虑属于不同部分的点对有多少，递归处理两个部分。

对$y$坐标分治，把两个部分中的点按$x$坐标从小到大排序，依次处理。假设处理到一个上半部分的点，当上半部分只有这个点时，下半部分可以与它构成友好点对的点的$y$坐标严格下降。因此我们可以对上半部分维护一个$y$坐标严格上升的单调栈，对下半部分维护一个$y$坐标严格下降的单调栈。在处理上半部分的某个点$p$时，用上半部分的单调栈找出$x$坐标最大的$y$坐标不大于它的点$q$，在下半部分的单调栈里二分出$x$坐标大于$q$的点有多少个，即是与$p$构成友好点对的点的个数。下半部分同理。

有一些细节：$y$坐标相同的点需放在同一部分，若某一部分中所有点的$y$坐标相同，则直接加上这一部分的答案，不递归处理；若有多个$x$坐标相同的点，上半部分只考虑$y$坐标最小的，下半部分只考虑$y$坐标最大的；两个部分中$x$坐标相同的点需同时处理。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
static int const MAX = 1000000001;
long long ans;
struct Point {
  int x, y;
  friend bool operator<(Point const &a, Point const &b) {
    return a.x < b.x;
  }
} p[N], s1[N], s2[N], tmp[N];

void calc(int l, int r) {
  if (l == r)
    return;
  int mid = (l + r) >> 1, L = mid - 1, R = mid + 1;
  for (; l <= L && p[L].y == p[mid].y; --L)
    ;
  for (; R <= r && p[R].y == p[mid].y; ++R)
    ;
  if (l > L && R > r) {
    std::sort(p + l, p + r + 1);
    return void(ans += r - l);
  }
  mid = l <= L ? L : R - 1;
  int p1 = l, p2 = mid + 1, p3 = l, t1 = 0, t2 = 0;
  calc(l, mid), calc(mid + 1, r);
  for (; p1 <= mid && p2 <= r;) {
    int x = std::min(p[p1].x, p[p2].x), mx = -MAX, mn = MAX;
    for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
      mx = std::max(mx, p[p1].y);
    for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
      mn = std::min(mn, p[p2].y);
    for (; t1 && s1[t1 - 1].y < mx; --t1)
      ;
    for (; t2 && s2[t2 - 1].y > mn; --t2)
      ;
    Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0}, r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
    for (; t1 && s1[t1 - 1].y == mx; --t1)
      ;
    for (; t2 && s2[t2 - 1].y == mn; --t2)
      ;
    if (mx > -MAX)
      ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
    if (mn < MAX)
      ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
  }
  for (; p1 <= mid;) {
    int x = p[p1].x, mx = -MAX;
    for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
      mx = std::max(mx, p[p1].y);
    for (; t1 && s1[t1 - 1].y < mx; --t1)
      ;
    Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0};
    for (; t1 && s1[t1 - 1].y == mx; --t1)
      ;
    ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
  }
  for (; p2 <= r;) {
    int x = p[p2].x, mn = MAX;
    for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
      mn = std::min(mn, p[p2].y);
    for (; t2 && s2[t2 - 1].y > mn; --t2)
      ;
    Point r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
    for (; t2 && s2[t2 - 1].y == mn; --t2)
      ;
    ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
  }
  for (int i = l; i <= r; ++i)
    p[i] = tmp[i];
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &p[i].x, &p[i].y);
  std::sort(p, p + n, [](Point const &a, Point const &b) { return a.y < b.y; });
  calc(0, n - 1), printf("%I64d\n", ans);
  return 0;
}