扫描线 + 离散化 + 排序哈希集合（升序），求解《850. 矩形面积 II》

var rectangleArea = function(rectangles) {
  const n = rectangles.length, ySegmentSet = new Set
  for (let i = 0; i < n; i++) ySegmentSet.add(rectangles[i][1]).add(rectangles[i][3])
  const ySegments = Array.from(ySegmentSet).sort((a, b) => a - b), ySegmentsLength = ySegments.length
  const overlaps = new Uint8Array(ySegmentsLength - 1), xTuples = new Array(n << 1)
  for (let i = 0; i < n; i++) xTuples.push([rectangles[i][0], i, 1], [rectangles[i][2], i, -1])
  xTuples.sort((a, b) => a[0] - b[0])
  let area = 0n
  for (let i = 0, j = 0; i < (n << 1) - 1; i = j) {
    for (j = i + 1; j < (n << 1) - 1; j++) if (xTuples[j][0] !== xTuples[i][0]) break
    for (let k = i; k < j; k++) {
      const [_, index, cnt] = xTuples[k]
      const bottom = rectangles[index][1], top = rectangles[index][3]
      for (let m = 0; m < ySegmentsLength - 1; m++) {
        if (ySegments[m] >= bottom && ySegments[m + 1] <= top) overlaps[m] += cnt
      }
    }
    let overlapLength = 0n
    for (let m = 0; m < ySegmentsLength - 1; m++) {
      if (overlaps[m] > 0) overlapLength += BigInt(ySegments[m + 1] - ySegments[m])
    }
    area += overlapLength * BigInt(xTuples[j][0] - xTuples[i][0])
  }
  return area % BigInt(1e9 + 7)
};

function rectangleArea(rectangles: number[][]): number {
  const n = rectangles.length, ySegmentSet = new Set<number>()
  for (let i = 0; i < n; i++) ySegmentSet.add(rectangles[i][1]).add(rectangles[i][3])
  const ySegments = Array.from(ySegmentSet).sort((a, b) => a - b)
  const ySegmentLength = ySegments.length, overlaps = new Uint8Array(ySegmentLength - 1), xTuples = new Array(n << 1)
  for (let i = 0; i < n; i++) xTuples.push([rectangles[i][0], i, 1], [rectangles[i][2], i, -1])
  xTuples.sort((a, b) => a[0] - b[0])
  let area = 0n;
  for (let i = 0, j = 0; i < (n << 1) - 1; i = j) {
    for (j = i + 1; j < (n << 1) - 1; j++) if (xTuples[j][0] !== xTuples[i][0]) break
    for (let k = i; k < j; k++) {
      const [_, index, cnt] = xTuples[k]
      const bottom = rectangles[index][1], top = rectangles[index][3]
      for (let m = 0; m < ySegmentLength - 1; m++) {
        if (ySegments[m] >= bottom && ySegments[m + 1] <= top) overlaps[m] += cnt
      }
    }
    let overlapLength = 0n
    for (let m = 0; m < ySegmentLength - 1; m++) {
      if (overlaps[m] > 0)  overlapLength += BigInt(ySegments[m + 1] - ySegments[m])
    }
    area += overlapLength * BigInt(xTuples[j][0] - xTuples[i][0])
  }
  return Number(area % BigInt(1e9 + 7))
};

class Solution {
  function rectangleArea($rectangles) {
    $n = count($rectangles);
    $ySegments = [];
    foreach ($rectangles as $r) array_push($ySegments, $r[1], $r[3]);
    $ySegments = array_unique($ySegments);
    sort($ySegments, SORT_NUMERIC);
    $ySegmentsLength = count($ySegments);
    $overlaps = array_fill(0, $ySegmentsLength - 1, 0);
    $xTuples = [];
    foreach ($rectangles as $i => $r) array_push($xTuples, [$r[0], $i, 1], [$r[2], $i, -1]);
    usort($xTuples, fn($a, $b) => $a[0] > $b[0]);
    $area = 0;
    for ($i = 0, $j = 0; $i < ($n << 1) - 1; $i = $j) {
      for ($j = $i + 1; $j < ($n << 1) - 1; $j++) if ($xTuples[$j][0] !== $xTuples[$i][0]) break;
      for ($k = $i; $k < $j; $k++) {
        list($_, $index, $cnt) = $xTuples[$k];
        $bottom = $rectangles[$index][1];
        $top = $rectangles[$index][3];
        for ($m = 0; $m < $ySegmentsLength - 1; $m++) {
          if ($bottom <= $ySegments[$m] && $top >= $ySegments[$m + 1]) $overlaps[$m] += $cnt;
        }
      }
      $overlapLength = 0;
      for ($m = 0; $m < $ySegmentsLength - 1; $m++) {
        if ($overlaps[$m] > 0) $overlapLength += $ySegments[$m + 1] - $ySegments[$m];
      }
      $area += $overlapLength * ($xTuples[$j][0] - $xTuples[$i][0]);
    }
    return $area % (1e9 + 7);
  }
}

func rectangleArea(rectangles [][]int) int {
  n, ySegmentSet := len(rectangles), map[int]struct{}{}
  for _, r := range rectangles {
    ySegmentSet[r[1]] = struct{}{}
    ySegmentSet[r[3]] = struct{}{}
  }
  ySegments, pos := make([]int, len(ySegmentSet)), 0
  for segment, _ := range ySegmentSet {
    ySegments[pos] = segment
    pos++
  }
  sort.Ints(ySegments)
  ySegmentsLength := len(ySegments)
  type tuple struct {x, index, cnt int}
  xTuples, overlaps, area := make([]tuple, n << 1), make([]int, ySegmentsLength - 1), 0
  for i, r := range rectangles {
    xTuples[i << 1] = tuple{r[0], i, 1}
    xTuples[i << 1 + 1] = tuple{r[2], i, -1}
  }
  sort.SliceStable(xTuples, func(i, j int) bool {
    return xTuples[i].x < xTuples[j].x
  })
  for i, j := 0, 0; i < n << 1 - 1; i = j {
    for j = i + 1; j < n << 1 - 1; j++ {
      if xTuples[j].x != xTuples[i].x {
        break
      }
    }
    for k := i; k < j; k++ {
      index, cnt := xTuples[k].index, xTuples[k].cnt
      bottom, top := rectangles[index][1], rectangles[index][3]
      for m := 0; m < ySegmentsLength - 1; m++ {
        if bottom <= ySegments[m] && top >= ySegments[m + 1] {
          overlaps[m] += cnt
        }
      }
    }
    overlapsLength := 0
    for m := 0; m < ySegmentsLength - 1; m++ {
      if overlaps[m] > 0 {
        overlapsLength += ySegments[m + 1] - ySegments[m]
      }
    }
    area += overlapsLength * (xTuples[j].x - xTuples[i].x)
  }
  return area % (1e9 + 7)
}

class Solution {
  public int rectangleArea(int[][] rectangles) {
    int n = rectangles.length;
    Set<Integer> ySegmentSet = new HashSet<Integer>();
    for (int[] r : rectangles) {
      ySegmentSet.add(r[1]);
      ySegmentSet.add(r[3]);
    }
    List<Integer> ySegments = new ArrayList<Integer>(ySegmentSet);
    Collections.sort(ySegments);
    int ySegmentsLength = ySegments.size();
    int[] overlaps = new int[ySegmentsLength - 1];
    List<int[]> xTuples = new ArrayList<int[]>();
    for (int i = 0; i < rectangles.length; i++) {
      xTuples.add(new int[]{rectangles[i][0], i, 1});
      xTuples.add(new int[]{rectangles[i][2], i, -1});
    }
    Collections.sort(xTuples, (a, b) -> a[0] - b[0]);
    long area = 0;
    for (int i = 0, j = 0; i < (n << 1) - 1; i = j) {
      for (j = i + 1; j < (n << 1) - 1; j++) {
        if (xTuples.get(j)[0] != xTuples.get(i)[0]) break;
      }
      for (int k = i; k < j; k++) {
        int index = xTuples.get(k)[1], cnt = xTuples.get(k)[2];
        int bottom = rectangles[index][1], top = rectangles[index][3];
        for (int m = 0; m < ySegmentsLength - 1; m++) {
          if (bottom <= ySegments.get(m) && top >= ySegments.get(m + 1)) overlaps[m] += cnt;
        }
      }
      long overlapsLength = 0;
      for (int m = 0; m < ySegmentsLength - 1; m++) {
        if (overlaps[m] > 0) overlapsLength += ySegments.get(m + 1) - ySegments.get(m);
      }
      area += overlapsLength * (xTuples.get(j)[0] - xTuples.get(i)[0]);
    }
    return (int)(area % 1000000007);
  }
}

public class Solution {
  public int RectangleArea(int[][] rectangles) {
    int n = rectangles.Length;
    ISet<int> ySegmentSet = new HashSet<int>();
    foreach (int[] r in rectangles) {
      ySegmentSet.Add(r[1]);
      ySegmentSet.Add(r[3]);
    }
    List<int> ySegments = new List<int>(ySegmentSet);
    ySegments.Sort();
    int ySegmentsLength = ySegments.Count;
    int[] overlaps = new int[ySegmentsLength - 1];
    List<Tuple<int, int, int>> xTuples = new List<Tuple<int, int, int>>();
    for (int i = 0; i < n; i++) {
      xTuples.Add(new Tuple<int, int, int>(rectangles[i][0], i, 1));
      xTuples.Add(new Tuple<int, int, int>(rectangles[i][2], i, -1));
    }
    xTuples.Sort((a, b) => a.Item1 - b.Item1);
    long area = 0;
    for (int i = 0, j = 0; i < (n << 1) - 1; i = j) {
      for (j = i + 1; j < (n << 1) - 1; j++) {
        if (xTuples[j].Item1 != xTuples[i].Item1) break;
      }
      for (int k = i; k < j; k++) {
        int index = xTuples[k].Item2, cnt = xTuples[k].Item3;
        int bottom = rectangles[index][1], top = rectangles[index][3];
        for (int m = 0; m < ySegmentsLength - 1; m++) {
          if (bottom <= ySegments[m] && top >= ySegments[m + 1]) overlaps[m] += cnt;
        }
      }
      long overlapsLength = 0;
      for (int m = 0; m < ySegmentsLength - 1; m++) {
        if (overlaps[m] > 0) overlapsLength += ySegments[m + 1] - ySegments[m];
      }
      area += overlapsLength * (xTuples[j].Item1 - xTuples[i].Item1);
    }
    return (int)(area % 1000000007);
  }
}

typedef struct {
  int key;
  UT_hash_handle hh;
} HashItem;
typedef struct {
  int x;
  int index;
  int cnt;
} Tuple;
static inline int cmp(const void* pa, const void* pb) {
  return *(int*)pa - *(int*)pb;
}
static inline int cmpTuples(const void* pa, const void* pb) {
   return (*(Tuple**)pa)->x - (*(Tuple**)pb)->x;
}
int rectangleArea(int** rectangles, int rectanglesSize, int* rectanglesColSize){
  HashItem* ySegmentSet = NULL;
  for (int i = 0; i < rectanglesSize; i++) {
    HashItem* pEntry = NULL;
    HASH_FIND_INT(ySegmentSet, &rectangles[i][1], pEntry);
    if (pEntry == NULL) {
      pEntry = malloc(sizeof(HashItem));
      pEntry->key = rectangles[i][1];
      HASH_ADD_INT(ySegmentSet, key, pEntry);
    }
    HASH_FIND_INT(ySegmentSet, &rectangles[i][3], pEntry);
    if (pEntry == NULL) {
      pEntry = malloc(sizeof(HashItem));
      pEntry->key = rectangles[i][3];
      HASH_ADD_INT(ySegmentSet, key, pEntry);
    }
  }
  int ySegmentsLength = HASH_COUNT(ySegmentSet);
  int* overlaps = malloc(sizeof(int) * (ySegmentsLength - 1));
  memset(overlaps, 0, sizeof(int) * (ySegmentsLength - 1));
  int* ySegments = malloc(sizeof(int) * ySegmentsLength);
  int pos = 0;
  HashItem *cur, *tmp;
  HASH_ITER(hh, ySegmentSet, cur, tmp) {
    ySegments[pos++] = cur->key;
  }
  qsort(ySegments, ySegmentsLength, sizeof(int), cmp);
  Tuple** xTuples = malloc(sizeof(Tuple*) * (rectanglesSize << 1));
  for (int i = 0; i < rectanglesSize; i++) {
    Tuple* tuple0 = malloc(sizeof(Tuple));
    tuple0->x = rectangles[i][0];
    tuple0->index = i;
    tuple0->cnt = 1;
    xTuples[i << 1] = tuple0;
    Tuple* tuple1 = malloc(sizeof(Tuple));
    tuple1->x = rectangles[i][2];
    tuple1->index = i;
    tuple1->cnt = -1;
    xTuples[(i << 1) + 1] = tuple1;
  }
  qsort(xTuples, rectanglesSize << 1, sizeof(Tuple*), cmpTuples);
  long area = 0;
  for (int i = 0, j = 0; i < (rectanglesSize << 1) - 1; i = j) {
    for (j = i + 1; j < (rectanglesSize << 1) - 1; j++) {
      if (xTuples[j]->x != xTuples[i]->x) break;
    }
    for (int k = i; k < j; k++) {
      int index = xTuples[k]->index, cnt = xTuples[k]->cnt;
      int bottom = rectangles[index][1], top = rectangles[index][3];
      for (int m = 0; m < ySegmentsLength - 1; m++) {
        if (bottom <= ySegments[m] && top >= ySegments[m + 1]) overlaps[m] += cnt;
      }
    }
    long overlapsLength = 0;
    for (int m = 0; m < ySegmentsLength - 1; m++) {
      if (overlaps[m] > 0) overlapsLength += ySegments[m + 1] - ySegments[m];
    }
    area += overlapsLength * (xTuples[j]->x - xTuples[i]->x);
  }
  return area % 1000000007;
}

class Solution {
public:
  int rectangleArea(vector<vector<int>>& rectangles) {
    int n = rectangles.size();
    unordered_set<int> ySegmentSet;
    for (const vector<int>& r : rectangles) {
      ySegmentSet.emplace(r[1]);
      ySegmentSet.emplace(r[3]);
    }
    vector<int> ySegments;
    ySegments.assign(ySegmentSet.begin(), ySegmentSet.end());
    sort(ySegments.begin(), ySegments.end());
    int ySegmentsLength = ySegments.size();
    vector<int> overlaps(ySegmentsLength - 1, 0);
    vector<tuple<int, int, int>> xTuples;
    for (int i = 0; i < n; i++) {
      xTuples.emplace_back(rectangles[i][0], i, 1);
      xTuples.emplace_back(rectangles[i][2], i, -1);
    }
    sort(xTuples.begin(), xTuples.end(), [](tuple<int, int, int> a, tuple<int, int, int> b)->bool {
      return get<0>(a) < get<0>(b);
    });
    long area = 0;
    for (int i = 0, j = 0; i < (n << 1) - 1; i = j) {
      for (j = i + 1; j < (n << 1) - 1; j++) {
        if (get<0>(xTuples[j]) != get<0>(xTuples[i])) break;
      }
      for (int k = i; k < j; k++) {
        auto& [_, index, cnt] = xTuples[k];
        int bottom = rectangles[index][1], top = rectangles[index][3];
        for (int m = 0; m < ySegmentsLength - 1; m++) {
          if (bottom <= ySegments[m] && top >= ySegments[m + 1]) overlaps[m] += cnt;
        }
      }
      long overlapsLength = 0;
      for (int m = 0; m < ySegmentsLength - 1; m++) {
        if (overlaps[m] > 0) overlapsLength += ySegments[m + 1] - ySegments[m];
      }
      area += overlapsLength * (get<0>(xTuples[j]) - get<0>(xTuples[i]));
    }
    return area % static_cast<int>(1e9 + 7);
  }
};

class Solution:
  def rectangleArea(self, rectangles: List[List[int]]) -> int:
    n, ySegementSet, area = len(rectangles), set(), 0
    for r in rectangles:
      ySegementSet.add(r[1])
      ySegementSet.add(r[3])
    ySegements, ySegementsLength = sorted(ySegementSet), len(ySegementSet)
    overlaps, xTuples = [0] * (ySegementsLength - 1), []
    for i, r in enumerate(rectangles):
      xTuples.append((r[0], i, 1))
      xTuples.append((r[2], i, -1))
    xTuples.sort(key = lambda v : v[0])
    i = 0
    while i < (n << 1) - 1:
      j = i + 1
      while j < (n << 1) - 1 and xTuples[j][0] == xTuples[i][0]: j += 1
      for k in range(i, j):
        _, index, cnt = xTuples[k]
        bottom, top = rectangles[index][1], rectangles[index][3]
        for m in range(0, ySegementsLength - 1):
          if bottom <= ySegements[m] and top >= ySegements[m + 1]: overlaps[m] += cnt
      overlapsLength = 0
      for m in range(0, ySegementsLength - 1):
        if overlaps[m] > 0: overlapsLength += ySegements[m + 1] - ySegements[m]
      area += overlapsLength * (xTuples[j][0] - xTuples[i][0])
      i = j
    return area % 1000000007