统计区间内的线段

一维区间
¶

问题简述
¶

坐标轴上存在 $N$ 条线段，有 $Q$ 次查询，每次查询询问与给定区间 $[a_{q}, b_{q}]$ 相交的线段数量。（相交指存在重叠的区域，包括相互包含的情况）

问题简析
¶

先对线段进行排序：左端点小的排在前面，左端点相同时，右端点小的排在前面。

记 $f (x)$ 为左端点在点 $x$ 上的线段条数， $g (x)$ 为右端点在 $x$ 上的线段条数。计算 $f (x)$ 和 $g (x)$ 可以通过扫描排好序的线段，不妨记当前扫描到的线段为 $[x 1, x 2]$ ，并执行下述操作：

$f (x 1) = f (x 1) + 1$
$g (x 2) = g (x 2) + 1$

在扫描的过程中，不难有：

区间左侧 $[- \infty, a_{q} - 1]$ 与当前区间不相交的数量为线段右端点个数，即 $\sum_{x = - \infty}^{a_{q} - 1} f (x)$ ；
区间右侧 $[b_{q} + 1, + \infty]$ 与当前区间不相交的数量为线段左端点个数，即 $\sum_{x = b_{q} + 1}^{+ \infty} g (x)$ ；

由容斥定理可知，与区间 $[a_{q}, b_{q}]$ 相交的线段数为

N - (\sum_{x = - \infty}^{a_{q} - 1} f (x) + \sum_{x = b_{q} + 1}^{+ \infty} g (x))

小结
¶

对区间进行排序（或标号），再维护两个前缀和就可以了。

时间复杂度： $O (N \log N + N)$
空间复杂度： $O (N)$

二维区间（离线查询）
¶

问题描述
¶

二维坐标系中存在 $N$ 条与坐标轴垂直或平行的线段；有 $Q$ 次查询，每次查询询问与给定矩形窗口 $W_{q} = {A_{q} (x 1_{q}, y 1_{q}), B_{q} (x 2_{q}, y 2_{q})}$ 相交的线段数量。其中，矩形窗口的边与坐标轴平行或垂直，且 $A_{q}$ 为矩形的左下角顶点， $B_{q}$ 为矩形的右上角对顶点。（相交指存在重叠的区域，包括相互包含的情况）

问题简析
¶

先仅考虑与 $y$ 轴平行的线段与 $W_{q}$ 相交情况。假设与 $y$ 轴平行的线段有 $N_{y}$ 条。记：

$f (y)$ 为上端点在点 $y$ 上的线段条数；
$g (y)$ 为下端点在 $y$ 上的线段条数，初始时 $f (y) = g (y) = 0$ ；
$h 1 (q)$ 表示窗口 $q$ 的左边界之左（不包括左边界）与区间 $[y 1_{q}, y 2_{q}]$ 相交的线段数，
$h 2 (q)$ 表示窗口 $q$ 的右边界之左（包括右边界）与区间 $[y 1_{q}, y 2_{q}]$ 相交的线段数；

不难发现 $h 2 (q) - h 1 (q)$ 即为与 $y$ 轴平行的线段中与 $W_{q}$ 相交的数量。

将所有的窗口按照左边界 $x$ 坐标从小到大排序，并维护一个单调队列 $S$ ；遍历排好序的窗口 $W_{i} = {A_{i} (x 1_{i}, y 1_{i}), B_{i} (x 2_{i}, y 2_{i})}$ 。

若 $S$ 中存在窗口（必在队首） $W_{k} = {A_{k} (x 1_{k}, y 1_{k}), B_{k} (x 2_{k}, y 2_{k})}$ 满足 $x 2_{k} < x 1_{i}$ ，执行下述操作，直到队列中没有这样的 $W_{k}$ ：
- 取出队首元素 $W_{k}$ ；
- 等待所有未操作过的且 $x$ 坐标小于等于 $x 2_{k}$ 的线段计入到 $f, g$ 中；
- 计算此时 $x$ 坐标在 $x 2_{k}$ 左侧的线段中，与区间 $[y 1_{k}, y 2_{k}]$ 相交的垂直线段条数：
  $h_{2} (k) = N_{y} - (\sum_{y = - \infty}^{y 1_{k} - 1} f (y) + \sum_{y = y 2_{k} + 1}^{+ \infty} g (x))$
- 则此时 $h_{2} (k) - h_{1} (k)$ 即为与 $y$ 轴平行的线段中与 $W_{k}$ 相交的数量。
将 $W_{i}$ 丢进 $S$ 队尾，并执行下述操作：
- 等待所有未操作过的且 $x$ 坐标小于 $x 1_{i}$ 的线段计入到 $f, g$ 中；
- 计算此时 $x$ 坐标在 $x 1_{i}$ 左侧的线段中，与区间 $[y 1_{i}, y 2_{i}]$ 相交的垂直线段条数：
  $h_{1} (i) = N_{y} - (\sum_{y = - \infty}^{y 1_{i} - 1} f (y) + \sum_{y = y 2_{i} + 1}^{+ \infty} g (x))$
- 继续遍历排好序的窗口 $W_{i}$ ；

类似地，可得到与窗口 $i$ 相交的水平线段的数量，做一次相加即可得到答案。

小结
¶

以统计窗口与平行于 $y$ 轴方向上的线段相交的数量为例，算法的思路是将当前需要考虑的线段限定在目标边界以左，则此时问题归约为垂直方向上统计某个区间内的线段数量，而这个区间内的线段有可能在目标窗口的左边界以左，但只使用一种类似前缀和的思想（参见前文中关于 $h_{1}$ 和 $h_{2}$ 的定义）将这部分线段再减去即可。

和一维问题的区别在于多了一个动态计入 $f, g$ 的步骤，因此可归约到【单点更新，区间求和】问题，维护一棵线段树或树状数组即可。

时间复杂度： $O (N \log N)$
空间复杂度： $O (N)$

二维区间（在线查询）
¶

和上一个问题类似，不同的是，每次查询需要立刻给出答案，即我们无法再对窗口进行排序了。

问题简析
¶

在离线查询的算法中，因为将查询窗口进行排序，所以每次计算窗口的左右边界时，天然地保证了当前考虑过的线段全在边界以左。如果我们增加一个额外的维度维护 $x$ 轴的信息，即能够快速地查询在某个 $x$ 轴左侧的线段的分布情况，则可解决本问题。

不难想到可以建立一棵主席树（可持久化线段树），每个版本为只包含某个特定的 $x$ 轴以左的线段下 $f$ 和 $g$ 的值，则查询时可以先查询到版本，然后再查询垂直方向上的线段相交情况。此外再建立线段树时，仅需考虑所有与 $y$ 轴平行的线段的 $x$ 值即可，之后给定了窗口后，可通过二分确定主席树中的版本号。

小结
¶

和离线查询的版本相比，把线段树换成了主席树，因此无论时间复杂度还是空间复杂度都需要再乘一个 $\log N$ 。此外，因为确定窗口边界所对应的主席树所对应的版本号需要进行一次二分，因此时间复杂度还需要再乘一个 $\log N$

时间复杂度： $O (N \log^{3} N)$
空间复杂度： $O (N \log N)$

一维区间¶

问题简述¶

问题简析¶

小结¶

二维区间（离线查询）¶

问题描述¶

问题简析¶

小结¶

二维区间（在线查询）¶

问题简析¶

小结¶

一维区间
¶

问题简述
¶

问题简析
¶

小结
¶

二维区间（离线查询）
¶

问题描述
¶

问题简析
¶

小结
¶

二维区间（在线查询）
¶

问题简析
¶

小结
¶