扫描线

二维数点，对于询问的$[l, r]$区间我们只需要统计有多少个数上一次出现的位置$pos$ 满足$pos \leq l$，即可。 template<class T> struct BIT { T c[N]; int size; void resize(int s) { size = s;} T qu ......

题目链接 218. 天际线问题 思路 参考宫水三叶大佬题解 代码 class Solution { public List<List<Integer>> getSkyline(int[][] buildings) { List<List<Integer>> result = new ArrayLis ......

P5490 【模板】扫描线 给你 n 个位于平面直角坐标系上的长方形，它们之间可能互相重叠，求这些长方形的面积。 很显然，对于长方形之间有重叠部分，如果采用容斥原理，不仅非常复杂，而且难以实现。 事实上，既然题目已经给了我们这些长方形的顶点，这些长方形最终构成的图形可以被坐标轴划分为 m 个长方形。 ......

 ![](https://img2023.cnblogs.com/blog/1161216/202303/1161... ......

研究对象 在一个B维直角坐标系下，第i维坐标在一个整数范围[li,ri]间，内部的点集称为一个B维正交范围。 一般1维正交范围简称区间，2维正交范围简称矩形，3维正交范围简称立方体 对于B维正交范围，每一维都有两个限制，即有两条边（side），这样是一个2B-side的B维正交范围 如果部分维只有一 ......