原理：沿 $x$ 轴，$y$ 轴交替依次按坐标点的中位数对半分开，直到只剩下一个点为止。
复杂度分析：考虑一条边只会横跨两个区间，所以沿坐标轴划分矩形数量与边界划分数量是同阶的。有 $T(n) = 2 \times T(\frac{n}{4}) + O(1)$，单次操作复杂度是 $\sqrt n$ 的。
例题：
$\mathbb{T1} \ \ \text{区间逆序对个数} \ ,n \le 5 \times 10 ^ 4$
$\mathbb{Q}$：询问 $[l,r]$ 的区间中逆序对的个数。
$\mathbb{A}$：扫描线，考虑升维，用 K-DT 维护平面点的个数。
$\mathbb{T2} \ \ \text{方方方的数据结构} $
题意：
给定长为 $n$ 的序列 $a$，有以下几种操作：
$1$： $∀i ∈ [l, r], a_i ← a_i + x$
$2$： $∀i ∈ [l, r], a_i ← a_i × x$
$3$： 求 $a_p \operatorname{mod} 998244353$
$4$： 撤销第 $p$ 个操作
$1 ≤ n, m ≤ 1.5 × 10^5$
$\mathbb{A}$：考虑升维。维护每个时间维度的序列 $a$。那么每个操作会影响一个区间，直接 K-DT 维护所有点是 $O(n\sqrt {n^2} = n^2)$ 的，所以我们只维护询问的点，复杂度 $O(n\sqrt{n})$。
$\mathbb{T3} \ \ \text{网上看到的题} $
题意：
给定长度为 $n$ 的序列 $a$ 和长度为 $n$ 的 $01$ 序列 $b$，每次操作给定
$x$，将所有 $a_i = x$ 的位置 $b_i ← b_i ⊕ 1$，每次操作后求 $b$ 有多少段连续的 $1$。
$1 ≤ n, m ≤ 5 × 10^4$
$\mathbb{A}$：直接维护段数不好做，考虑维护“断点”。向两端放两个 $0$，相邻 $01$、$10$ 的数量除以 $2$ 就是答案。我们把 $(a_i,a_{i+1})$ 放到平面，每次修改一条横线，一条竖线修改。
$\text{ps}$：这个维护“断点”的 $\text{trick}$ 比较常用。
$\mathbb{T4} \ \ \text{好像是 SOJ 的题} $
题意：
有一个长为 $4^n$ 的数组 $a$，有以下几种操作：
$1$： 给定 $l, r, ∀i ∈ [l, r], a_i ← \left \lfloor \sqrt{a_i} \right \rfloor $
$2$： 给定 $l, r, v, ∀i ∈ [l, r], a_i ← a_i + v$
$3$： 给定 $l, r, \text{求} ∑ ^{r}_{i = l} a_i$
$4$： $∀i < \operatorname{rev}(i),\operatorname{swap}(a_i, a_{\operatorname{rev}(i)}),\operatorname{rev}(i)$ 表示 $i$ 二进制逆序的结果，如 $n = 2$ 时 $\operatorname{rev}(7) = 14$
$1 ≤ n ≤ 9, 1 ≤ m ≤ 3 × 10^4$
$\mathbb{A}$：升维，维护 $(a_i, a_{\operatorname{rev}(i)})$，第 $4$ 个操作相当于交换坐标轴。第 $1$ 个操作运用势能分析可证明总复杂度是 $\sqrt{n} \times \log_2v$ 的。
$\mathbb{T5} \ \ \text{rrusq} $
题意：
平面上给定大小为 $n$ 的点集 $a$，点有点权，给定 $m$ 个矩形 $b_{1,···,m}$，有 $q$ 次询问，每次询问 $b_{l,··· ,r}$ 的所有矩形所覆盖的点权值之和。
$1 ≤ n, m ≤ 10^5, 1 ≤ q ≤ 10^6$
$\mathbb{A}$：
首先考虑序列上的弱化版。
咕咕咕