离线排序与扫描线

在处理二维平面上的点集或矩形覆盖问题时，如果我们强行在二维空间中枚举和检查，往往会面临 $O(N^2)$ 甚至更高的复杂度，在几十万的数据面前直接超时。

遇到这类问题，别急着去找树套树等沉重的“二维数据结构”。我们不妨换个思路：能不能通过剥洋葱式的降维拆解，把一维交给“时间（排序）”，另一维交给一维数据结构？

这一讲，我们将通过“离线处理”与“扫描线”的经典模型，带你体验把二维问题拍扁成一维的降维打击。

一、在线与离线：拥有“预知未来”的超能力

在算法竞赛中，“在线”和“离线”不是指连没连网。

• 在线（Online）：用户问一个，你答一个。你不知道未来的询问是什么，必须当场给出答案。
• 离线（Offline）：题目一次性给了你所有的初始数据和询问，而且后一个询问不依赖前一个询问的答案。

面对离线题目，我们就拥有了“预知未来”的超能力！我们可以打破时间线，把所有询问打乱重排，按照对算法最有利的顺序去处理它们，最后再把答案按照原编号重新组装输出。用户看到的结果完全没变，但我们在底层干活的顺序已经发生了翻天覆地的变化。

二、第一层降维打击：把一半条件交给排序

我们先来看一个最基础的二维数点问题：平面上有若干个点，问有多少个点满足 $x \le X$ 且 $y \le Y$？（记作 $F(X,Y)$，相当于求二维前缀和）。

既然是离线询问，我们不必每次都去傻傻遍历所有点。

核心思想（扫描线雏形）：

1. 把所有的点按 $x$ 坐标从小到大排序。
2. 把所有的询问按 $X$ 阈值从小到大排序。
3. 想象一条垂直的扫描线从左向右扫。当我们要回答阈值为 $X$ 的询问前，就让扫描线移动到 $X$，并顺手把所有横坐标 $x \le X$ 的点“激活”（加入到一个结构中）。
4. 既然已经被激活，说明这些点的 $x$ 维条件已经永久满足。接下来，我们只需要在这个结构里查询：有多少个点的纵坐标 $y \le Y$ 即可！

二维问题被我们瞬间剥掉了一维，剩下的就是一个纯粹的一维前缀计数问题，树状数组完美接手。

1. 让我们用四个点手推一遍

假设有四个点：(1,2)、(2,1)、(2,3)、(2,3)。注意，后两个坐标相同但算两个独立的点，离散化时千万不要把点给去重了。

• 询问 F(1,3)：扫描线走到 1，只激活 (1,2)。此时树状数组里只有它，查询 $y \le 3$，答案为 1。
• 询问 F(2,2)：扫描线走到 2，另外三个点全被激活加入了树状数组。但在所有激活的点中，满足 $y \le 2$ 的只有 (1,2) 和 (2,1)，答案为 2。
• 询问 F(2,3)：扫描线不需要再移动，四个点都在结构里。查询 $y \le 3$，四个都满足，答案为 4。

纵坐标去重后离散化为 ys=[1,2,3]，树状数组维护这些位置的频次。每次查询 $Y$ 时，用 upper_bound 找不大于 $Y$ 的坐标有几个（假设为 k），查 sum(k) 即可。如果空前缀，自然返回 0。

这里的 add、sum，就是《树状数组》里的单点更新 update 和前缀查询 query；第一份程序把每次更新固定成加 1。

三、边界的恶魔：同坐标到底谁先动？

写离线扫描线，最容易死在等于号上。假设只有一个点 (2,3)，询问也是 F(2,3)。如果你先回答询问再加点，答案就会算成 0，因为横坐标为 2 的点还没来得及激活！

我们在写双指针或把事件混合排序时，必须明确同横坐标的先后关系。诀窍是先看题目的不等号：

不要盲目背诵“扫描线永远先加后问”。画出不等号，安排好逻辑，就能彻底告别那些莫名其妙差 1 的玄学 Bug。

四、拆解普通矩形：二维容斥的“四个分身”

如果询问不是前缀，而是一个正儿八经的闭矩形 $[a,c] \times [b,d]$ 呢？

很简单，利用二维容斥，把一个矩形询问拆成四个前缀询问：右上角 $-$ 左边 $-$ 下边 $+$ 左下角（加回来是因为被减了两次）。

每一个矩形生成四个独立的小询问，分别带上 +1、-1、-1、+1 的系数。离线跑完后，把四个小询问的结果乘以系数，累加到原本的 ans[id] 里。

1. 完整程序一：静态二维矩形数点

输入输出协议与数据范围： 输入第一行 n q，随后 n 行给点坐标 x y，最后 q 行给矩形 a b c d（保证 $a \le c, b \le d$）。输出每个闭矩形内的点数，包含边界，重合点分别计数。 支持 $0 \le n \le 5\times 10^5$、$1 \le q \le 5\times 10^5$。所有坐标都是 $[-10^9, 10^9]$ 内的整数。

课堂样例输入：

4 3
1 2
2 1
2 3
2 3
1 1 2 2
2 3 2 3
-1 -1 0 0

输出：

2
2
0

核心代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 500005;
const int M = 2000005; // 4倍询问数量

struct Point { int x, y; } p[N];
struct Query { int x, y, id, s; } e[M];

int ys[N], c[N];
int ans[N];
int n, q, cnt_e, cnt_y;

// 树状数组常规操作
void add(int x, int limit) {
    for(; x <= limit; x += x & -x) c[x]++;
}

int sum(int x) {
    int res = 0;
    for(; x > 0; x -= x & -x) res += c[x];
    return res;
}

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
        ys[++cnt_y] = p[i].y; // 收集y坐标用于离散化
    }
    
    // 纵坐标离散化去重
    sort(ys + 1, ys + cnt_y + 1);
    cnt_y = unique(ys + 1, ys + cnt_y + 1) - (ys + 1);

    // 点集按x从小到大排序
    sort(p + 1, p + n + 1, [](const Point& a, const Point& b) {
        return a.x < b.x;
    });

    // 读入矩形并拆解为四个事件
    for(int i = 1; i <= q; i++) {
        int a, b, c_x, d;
        cin >> a >> b >> c_x >> d;
        e[++cnt_e] = {c_x, d, i, 1};
        e[++cnt_e] = {a - 1, d, i, -1};
        e[++cnt_e] = {c_x, b - 1, i, -1};
        e[++cnt_e] = {a - 1, b - 1, i, 1};
    }
    
    // 询问按x阈值排序
    sort(e + 1, e + cnt_e + 1, [](const Query& a, const Query& b) {
        return a.x < b.x;
    });

    // 扫描线双指针推进
    int j = 1;
    for(int i = 1; i <= cnt_e; i++) {
        // 先加点（x <= X）
        while(j <= n && p[j].x <= e[i].x) {
            int k = lower_bound(ys + 1, ys + cnt_y + 1, p[j].y) - ys;
            add(k, cnt_y);
            j++;
        }
        // 后查询（y <= Y）
        int k = upper_bound(ys + 1, ys + cnt_y + 1, e[i].y) - ys - 1;
        ans[e[i].id] += e[i].s * sum(k);
    }

    // 离线按原顺序输出
    for(int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

四倍询问仍是 $O(Q)$ 个事件，整体复杂度极其优秀，为 $O((N+Q)\log(N+Q))$。

五、扫描线完全体：不数点，算面积（矩形面积并）

现在情况升级了。给的不是散点，而是多个互相交叠的矩形，求它们盖在地上的总面积。重叠部分只能算一次。

这时，我们真的需要拿一根竖直的“扫描线”从左往右扫过去。 随着扫描线的推进，矩形的左边界会让线段的覆盖长度增加，右边界会让覆盖长度减少。

由于只有经过矩形左右边界时，纵向的覆盖关系才会发生变化，所以在相邻两个事件之间，扫描线上的覆盖长度是恒定不变的！

例如矩形 $A=[0,3)\times[0,2)$，$B=[2,5)\times[1,4)$。

• 扫过 $[0,2)$ 时，只有 A，纵向长度为 2，面积为 $2 \times 2 = 4$；
• 扫过 $[2,3)$ 时，A和B合体 $[0,4)$，纵向长度为 4，面积为 $4 \times 1 = 4$；
• 扫过 $[3,5)$ 时，A退出只剩 B，纵向长度为 3，面积为 $3 \times 2 = 6$。 总面积就是 14。

六、线段树的物理意义转换：我们维护的是“段”不是“点”

面积并扫描线的灵魂，在于使用线段树来维护当前的纵向覆盖长度。 但请注意，此时线段树的叶子节点不再代表孤立的“点”，而是代表离散化后的两个相邻坐标构成的“线段区间”。

如果去重后的纵坐标序列是 ys = {0, 1, 2, 4}，那么三个叶子节点分别代表 $[0,1)$，$[1,2)$，$[2,4)$。 节点 $u$ 维护叶子编号 $[l, r]$ 时，它物理上代表的真实整段长度是 ys[r+1] - ys[l]。

1. 两个灵魂数组：cover 与 len

• cover[u]：记录当前节点代表的区间，被完整矩形边覆盖了多少层。
• len[u]：记录当前节点代表的区间内，实际被盖住的有效物理长度。

如何更新信息？（请细品这段无 pushdown 的优雅逻辑）

1. 如果 cover[u] > 0：说明至少有一块大矩形死死盖住了这整段！不用管下面子节点怎样了，当前有效长度直接拉满 len[u] = ys[r+1] - ys[l]。
2. 如果 cover[u] == 0：大矩形撤走了，但这并不意味着下面全空了（可能还有小矩形在局部苟着）。
   • 如果是叶子节点：没子节点可查了，len[u] = 0。
   • 如果是内部节点：它的有效长度就是左右儿子的有效长度之和，len[u] = len[左] + len[右]。

我们不需要写 pushdown！因为完整覆盖被直接登记在了高层节点，当高层的 cover 被撤销清零时，下面的子节点由于没有被破坏，会自动把局部的 len 重新“露”上来。这就是线段树区间的魅力所在。

下面的 pull 就是《线段树》里 pushup 的角色：根据当前覆盖层数和孩子的信息，重新算好本节点的 len。

2. 完整程序二：矩形面积并

输入输出协议与数据范围： 输入第一行 n，随后 n 行 x1 y1 x2 y2。 约定 $0 \le n \le 10^5$，坐标在 $[-10^9, 10^9]$ 内，且保证 $x_1 \le x_2, y_1 \le y_2$。零宽或零高的退化矩形需内部忽略。输出覆盖总面积。 覆盖总面积可能达到 $4 \times 10^{18}$，必须全程使用有符号 long long 防溢出。

课堂样例输入：

2
0 0 3 2
2 1 5 4

输出：

14

核心代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200005; // 最多 2e5 个事件和 y 坐标

struct Event { 
    int x, y1, y2, v; 
} e[N];

int ys[N];
// 线段树开4倍空间，这里基础段是 N，所以是 N<<2
int cover[N<<2], len[N<<2]; 
int n, cnt_e, cnt_y;

// 灵魂函数：更新有效长度
void pull(int u, int l, int r) {
    if (cover[u] > 0) {
        // 整段被完全覆盖，长度拉满
        len[u] = ys[r + 1] - ys[l];
    } else if (l == r) {
        // 叶子节点且未被盖住
        len[u] = 0;
    } else {
        // 局部覆盖露出来了，合并左右儿子
        len[u] = len[u << 1] + len[u << 1 | 1];
    }
}

void add(int u, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
        cover[u] += v;
        pull(u, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) add(u << 1, l, mid, ql, qr, v);
    if (qr > mid)  add(u << 1 | 1, mid + 1, r, ql, qr, v);
    pull(u, l, r);
}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2 || y1 == y2) continue; // 过滤退化矩形
        
        // 矩形左边：覆盖层数 +1；右边：覆盖层数 -1
        e[++cnt_e] = {x1, y1, y2, 1};
        e[++cnt_e] = {x2, y1, y2, -1};
        ys[++cnt_y] = y1;
        ys[++cnt_y] = y2;
    }

    if (cnt_e == 0) {
        cout << 0 << '\n';
        return;
    }

    // 纵坐标离散化
    sort(ys + 1, ys + cnt_y + 1);
    cnt_y = unique(ys + 1, ys + cnt_y + 1) - (ys + 1);

    // 事件按横坐标排序
    sort(e + 1, e + cnt_e + 1, [](const Event& a, const Event& b) {
        return a.x < b.x;
    });

    int m = cnt_y - 1; // m 个基础“段”
    int ans = 0, pre = e[1].x;
    int i = 1;

    while (i <= cnt_e) {
        int x = e[i].x;
        // 1. 先用旧的覆盖长度，结算左侧这块竖带的面积
        ans += len[1] * (x - pre);
        
        // 2. 把当前横坐标上所有的进入和离开事件全部执行
        while (i <= cnt_e && e[i].x == x) {
            int l = lower_bound(ys + 1, ys + cnt_y + 1, e[i].y1) - ys;
            int r = lower_bound(ys + 1, ys + cnt_y + 1, e[i].y2) - ys;
            // 注意：物理上操作的是 [l, r-1] 这几段基础段
            add(1, 1, m, l, r - 1, e[i].v);
            i++;
        }
        pre = x;
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

同横坐标的事件必须在一个 while 循环里“整组处理”。因为不管你是先加还是先减，在这个横坐标产生的面积跨度都是 0（即 x - pre = 0），只有当这一批状态全部登记完毕后，留下的 len 才会稳稳地用于下一条宽度的面积乘法。

整体时间复杂度为优秀的 $O(N \log N)$。

七、矩形面积并：为何不能用普通区间和维护长度

很多同学学完线段树后，第一反应是：面积并就是区间加 1、区间减 1，查询时不就是找“值大于 0 的总长度”吗？为什么不直接打 tag 然后写 pushdown 呢？

根本原因：操作缺乏“线性可加性”。 在区间加、区间求和的模板里，给区间每个数 $+1$，总和就会稳定增加 1 * 长度，所以能直接更新整段的统计值。

但是，“大于 0 的覆盖长度”并不是线性的。假设某段区间左半部分已被覆盖（值为 1），右半部分未被覆盖（值为 0）。如果现在有个大矩形把整段区间都 $+1$：

• 左半部分的值变成 2，但它贡献的“有效长度”毫无变化。
• 右半部分的值变成 1，它贡献的“有效长度”增加了。

同一个 $+1$ 操作，对内部不同状态的子区间产生的影响完全不同。若节点只存当前的覆盖长度，就不能照搬“区间和加上 增量 * 长度”的公式来处理所有增减；尤其撤去一层覆盖时，只看这个长度，不知道哪些地方还盖着别的矩形。如果因此每次都下探到叶子逐一检查，处理 $N$ 个矩形的总时间就可能退化为 $O(N^2)$。问题不在于 pushdown 本身不能用，而在于节点存的信息够不够。

这正是引入 cover 与 len 数组的原因。我们放弃记录“每个点具体被盖了多少次”，只维护“这一整段有没有被彻底封死”。只要 cover > 0，就知道整段长度有效；cover == 0 时，直接向左右儿子要它们组合后的局部 len。配合必定成对出现的 $+1$ 与 $-1$，这套免 pushdown 的机制巧妙绕过了普通区间和的陷阱。

八、统一事件优先级：处理同坐标先后顺序

在之前的二维点集查询中，我们讨论了“同横坐标到底谁先动”的边界逻辑，这往往需要双指针和嵌套 while 循环去分离点数组和查询数组。

与其小心翼翼地维护两组数据，不如将所有元素拉平，封装成同一种“事件”，通过排序的优先级来实现统一判断。

定义统一的 Event 结构体： 无论它是原图上的点，还是用户的查询，甚至矩形的入边和出边，全部放进同一个数组中。我们可以给事件赋予一个 type 属性，通过它直接区分优先级。

例如，题目要求查找 $x \le X, y \le Y$ 的点数。在这个不等号下，当坐标重合时，点必须在查询前先生效。我们规定：加点事件 type = 0，查询事件 type = 1。

重载比较运算符：

struct Event {
    int x, y, id, type;
    bool operator<(const Event& b) const {
        if (x != b.x) return x < b.x;
        // 横坐标相同时，type 小的事件排在前面优先触发
        return type < b.type;
    }
};

在主程序里，只需要给这个巨大的事件流排序一次，然后用一个干净的 for 循环从头扫到尾。遇到 type == 0 就更新树状数组，遇到 type == 1 就统计答案。不用纠结到底怎么写 while 才能不漏掉最后几个点。只要规则定好，sort 会自然地处理好所有冲突。

九、选学：离线求区间不同数

场景：给定一个长度为 $N$ 的数组，有 $Q$ 次询问，每次求区间 $[L, R]$ 里有多少个不同的数字。

暴力痛点：由于数字可能重复，我们无法用普通的前缀和相减（即 sum[R] - sum[L-1]）得出答案。同一个数字在区间内出现多次只能算一次。

既然允许离线，我们可以把所有的查询按右端点 $R$ 从小到大排序。 想象扫描线从左向右遍历原数组。对于任意一个数字（比如数字 1），如果它在前面出现过，现在又出现了，那么对于右端点延伸到现在的查询来说，前面那个旧的 1 已经无效了，只有最新出现的 1 才是有效的。

状态含义与推导：

1. 建立一个树状数组，里面维护的不是原始数值，而是位置的有效性（有效为 1，过期或为空为 0）。
2. 用数组 last_pos 记录每个数字上一次出现的位置下标。
3. 从左向右遍历数组，走到位置 $i$（数字为 $val$）时：
   • 如果 $val$ 以前出现过（last_pos[val] != 0），我们在树状数组的旧位置处 -1（抹除旧记录）。
   • 在树状数组的当前位置 $i$ 处 +1（激活新记录）。
   • 更新 last_pos[val] = i。
4. 回答询问：当扫描线刚好走到某个查询的右端点 $R$ 时，树状数组里所有的数字都只在它最靠右的位置保留了一个 1。此时直接查询树状数组中 $[L, R]$ 的区间和，得到的正是该区间内不同数字的个数。

1. 一个手算小例子

数组 1 2 1 3。

• $i=1 (val=1)$：树状数组变成 [1, 0, 0, 0]，last_pos[1]=1。
• $i=2 (val=2)$：树状数组变成 [1, 1, 0, 0]，last_pos[2]=2。
• $i=3 (val=1)$：数字 1 再次出现。旧位置 1 失效，新位置 3 激活。树状数组变为 [0, 1, 1, 0]，last_pos[1]=3。 如果此时有查询 $[1, 3]$，我们查 sum[3] - sum[0] = 2，对应唯一的 1 和 2，答案正确。

2. 完整程序实现

输入输出协议与数据范围： 输入第一行 n q，接下来一行 n 个正整数表示数组元素；之后 q 行，每行 l r 描述一次查询（保证 $1 \le l \le r \le n$）。输出共 q 行。 支持 $1 \le n, q \le 5\times 10^5$，数组元素保证在 $1$ 到 $5\times 10^5$ 范围内，可以直接用定长数组做 last_pos 以提升速度。如果值域较大，可将 last_pos 换为 map<int, int>。

课堂样例输入：

4 2
1 2 1 3
1 2
1 3

输出：

2
2

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 500005;

int a[N];
int c[N];
int last_pos[N]; // 记录数值上一次出现的位置
int ans[N];
int n, q;

struct Query {
    int l, r, id;
} e[N];

void add(int x, int v) {
    for(; x <= n; x += x & -x) c[x] += v;
}

int sum(int x) {
    int res = 0;
    for(; x > 0; x -= x & -x) res += c[x];
    return res;
}

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= q; i++) {
        cin >> e[i].l >> e[i].r;
        e[i].id = i;
    }
    
    // 按查询右端点 R 从小到大排序
    sort(e + 1, e + q + 1, [](const Query& A, const Query& B){
        return A.r < B.r;
    });
    
    int j = 1; 
    // 向右扫描数组原序列
    for(int i = 1; i <= n; i++) {
        int val = a[i];
        
        if (last_pos[val] != 0) {
            // 抹除旧位置的贡献
            add(last_pos[val], -1);
        }
        // 在当前最新位置登记贡献
        add(i, 1);
        last_pos[val] = i;
        
        // 集中处理所有右端点刚好到 i 的查询
        while (j <= q && e[j].r == i) {
            ans[e[j].id] = sum(e[j].r) - sum(e[j].l - 1);
            j++;
        }
    }
    
    for(int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

3. 对应实战

洛谷 P1972 [SDOI2009] HH 的项链

• 训练指引：经典的区间不同数模板题。提交原题时，长度、询问数和数值上限都到 $10^6$，要把 N 扩到 1000005，这样 a、c、last_pos、ans 和询问数组才都装得下。本节程序采用自拟的 n q 输入协议；原题是先读 n 和整个数组，再读询问数，记得把 q 的读入挪到数组之后。需要注意题目卡常，可以配合 ios::sync_with_stdio(0)。

十、渐进式实战练习题单

下一次看到题目里抛出一堆二维条件时，先问自己一句：我能不能对其中一维排序，做降维打击？ 如果扫过去以后剩下的是“数量叠加”，就用树状数组维护频次；如果剩下的是“连续几何覆盖”，就用线段树维护原坐标距离。

1. 洛谷 P2163 [SHOI2007] 园丁的烦恼

   • 训练指引：完美的二维静态数点模板题。把树木当作点，询问区域用二维容斥拆成四个，默写程序一。

2. 洛谷 P5490 【模板】扫描线 & 矩形面积并

   • 训练指引：默写程序二，牢记线段树底层 pull 的逻辑，体会“不写 pushdown”的清爽感，彻底搞懂为什么更新的是 [l, r-1]。