AtCoder ABC457-E 复盘：区间并集判定、结构分类与离线树状数组

前言

这题是 AtCoder Beginner Contest 457 的 E 题。比赛时没有完整写出来，赛后重新复盘时才意识到，瓶颈并不只是“会不会用树状数组”，而是要先把“两块布的覆盖范围恰好等于询问区间”这个条件拆成可判定的结构。

我一开始主要沿着左右端点拼接的方向思考，但对完整区间 [S,T] 与内部区间组合的情况处理得不够清晰。复盘之后，将所有合法方案划分为两类，再分别使用端点分组二分与离线树状数组处理，整体逻辑就顺畅了很多。

这篇文章记录这道题从题意建模、结构分类，到最终数据结构实现的完整推导过程。

---

题意抽象

本题给定 $N$ 个横向排列的格子，以及 $M$ 块布。第 $i$ 块布覆盖一个闭区间：

$$[L_i,R_i]$$

接下来有 $Q$ 个询问。每个询问给定一个目标区间：

$$[S,T]$$

需要判断是否可以从 $M$ 块布中恰好选择两块布，使得：

• $S$ 到 $T$ 的所有格子都被至少一块布覆盖；
• 不在 $[S,T]$ 中的格子不能被覆盖；
• 必须恰好选择两块布，不能只选择一块。

把每块布看作一个区间后，题目可以等价转化为：

是否存在两个不同的区间，使它们的并集恰好等于 $[S,T]$。

也就是判断是否存在两块布 $A$ 和 $B$，满足：

$$A\cup B=[S,T]$$

这个转化之后，几个必要条件会变得很明确：

• 两块布都不能越过 $[S,T]$；
• 左端点 $S$ 必须被覆盖；
• 右端点 $T$ 必须被覆盖；
• 两块布必须来自不同的布。

后续所有判定，本质上都是围绕这几个条件展开。

---

从端点约束出发

如果两个区间的并集恰好是 $[S,T]$，那么左端点 $S$ 一定要被覆盖。

又因为不能覆盖到 $S$ 左侧，所以覆盖 $S$ 的那块布只能从 $S$ 开始，即形如：

$$[S,x]$$

同理，右端点 $T$ 也必须被覆盖。由于不能覆盖到 $T$ 右侧，所以覆盖 $T$ 的那块布只能以 $T$ 结束，即形如：

$$[y,T]$$

如果这两块布之间没有断点，就需要满足：

$$x+1\ge y$$

于是，一个很自然的判定方向是：

• 找一块从 $S$ 开始、右端点尽量靠右的布；
• 找一块以 $T$ 结束、左端点尽量靠左的布；
• 判断二者是否能够连续覆盖整个 $[S,T]$。

不过这里存在一个细节：不能直接允许完整区间 $[S,T]$ 同时作为左侧布和右侧布。

如果存在一块布正好是 $[S,T]$，那么它既满足“从 $S$ 开始”，也满足“以 $T$ 结束”。但题目要求恰好选择两块不同的布，不能把同一块布重复使用两次。

因此，在普通的左右拼接判定中，可以额外要求：

$$x<T$$ $$y>S$$

也就是左侧布不能单独覆盖到 $T$，右侧布也不能从 $S$ 开始。这样可以自然排除“同一块完整区间被重复使用”的非法情况。

---

合法结构分类

经过上面的端点分析，对于一个询问 $[S,T]$，所有合法方案可以拆成两类。

左右拼接

存在两块布：

$$[S,x]$$

和：

$$[y,T]$$

并且满足：

$$x<T$$ $$y>S$$ $$x+1\ge y$$

其中，$x<T$ 和 $y>S$ 用来排除完整区间 $[S,T]$ 被当作两块布重复使用的情况；最后的 $x+1\ge y$ 则保证两块布之间不存在空隙，可以完整覆盖目标区间。

完整区间加内部区间

另一类情况是，存在一块布本身就是完整区间：

$$[S,T]$$

如果已经有这样一块布，那么另一块布只要完全落在 $[S,T]$ 内部即可。也就是说，另一块布 $[L_i,R_i]$ 只需要满足：

$$L_i\ge S$$ $$R_i\le T$$

此时一定有：

$$[S,T]\cup [L_i,R_i]=[S,T]$$

由于题目要求选择两块不同的布，所以完全包含在 $[S,T]$ 内部的布数量必须至少为 $2$。

这里的 $2$ 包括完整区间 $[S,T]$ 自身。换句话说，如果 $[S,T]$ 存在，并且内部区间数量大于 $1$，就说明除了完整区间本身之外，还存在另一块可以一起选择的布。

---

左右拼接的查询

为了快速判断第一类结构，预处理两个端点分组数组：

vector<int> L[maxn], R[maxn];

其中：

• L[x] 存储所有左端点为 x 的布的右端点；
• R[x] 存储所有右端点为 x 的布的左端点。

读入一块布 $[l,r]$ 时：

L[l].push_back(r);
R[r].push_back(l);

随后对每个 L[i] 和 R[i] 排序。

对于询问 $[S,T]$，左右拼接需要找到：

• L[S] 中严格小于 $T$ 的最大右端点 $x$；
• R[T] 中严格大于 $S$ 的最小左端点 $y$。

前者可以通过：

auto it_r = lower_bound(L[S].begin(), L[S].end(), T);

lower_bound 返回第一个大于等于 $T$ 的位置，因此向前移动一位，就得到严格小于 $T$ 的最大右端点。

后者可以通过：

auto it_l = upper_bound(R[T].begin(), R[T].end(), S);

upper_bound 返回第一个大于 $S$ 的位置，也就是需要的最小左端点 $y$。

如果二者都存在，并且满足：

$$x+1\ge y$$

那么左右拼接成立。

对应函数如下：

bool Joint(int l, int r) {
    if (L[l].empty() || R[r].empty()) {
        return false;
    }
    auto it_r = lower_bound(L[l].begin(), L[l].end(), r);
    auto it_l = upper_bound(R[r].begin(), R[r].end(), l);
    if (it_r == L[l].begin() || it_l == R[r].end()) {
        return false;
    }
    --it_r;
    return *it_r + 1 >= *it_l;
}

这一部分只负责判断第一类结构，即左右两端分别由两块非完整区间拼接而成。

---

完整区间与内部区间的查询

第二类结构需要同时判断两件事：

1. 是否存在完整区间 $[S,T]$；
2. 完全包含在 $[S,T]$ 内部的布是否至少有两块。

先处理第一件事。

读入每块布时，将区间 $[L,R]$ 编码成一个 long long，放入集合中：

ll Key(int l, int r) {
    return 1ll * l * maxn + r;
}

由于本题中 $L,R\le 2\times 10^5$，而 maxn 大于所有可能的右端点，所以这个编码可以唯一表示一个区间。

读入时：

exact_LR.insert(Key(l, r));

查询时：

exact_LR.count(Key(S, T))

即可判断是否存在一块布正好是 $[S,T]$。

接下来处理第二件事，也就是统计完全包含在 $[S,T]$ 内部的布数量。

对于询问 $[S,T]$，需要统计满足：

$$L_i\ge S$$

且：

$$R_i\le T$$

的布数量。

这是一个二维偏序统计问题。如果对每个询问暴力枚举所有布，复杂度会达到 $O(MQ)$，显然无法通过。

考虑离线处理。

将所有询问按照 $S$ 从大到小排序。处理当前询问 $[S,T]$ 时，将所有左端点满足：

$$L_i\ge S$$

且尚未加入过的布加入树状数组。

加入一块布 $[L_i,R_i]$ 时，在树状数组的 $R_i$ 位置加一：

bit.add(R_i);

这样，树状数组维护的就是：

当前所有左端点已经满足 $L_i\ge S$ 的布，它们的右端点分布。

此时查询：

bit.query(T)

得到的就是当前已加入的布中，满足：

$$R_i\le T$$

的数量。

由于这些布在加入时已经保证：

$$L_i\ge S$$

所以 bit.query(T) 统计的正是：

$$L_i\ge S,\quad R_i\le T$$

的布数量，也就是完全包含在 $[S,T]$ 内部的布数量。

对应扫描过程如下：

Fenwick bit(n);
int cur_L = n;

for (Query qy : Q) {
    while (cur_L >= qy.l) {
        for (int r : L[cur_L]) {
            bit.add(r);
        }
        cur_L--;
    }

    // 此时 bit.query(qy.r) 就是 insideCount(qy.l, qy.r)
}

因此第二类结构的判定条件为：

exact_LR.count(Key(l, r)) && bit.query(r) > 1

其中 bit.query(r) > 1 表示完全包含在 $[l,r]$ 内的布至少有两块。因为完整区间 $[l,r]$ 本身已经算一块，所以大于 $1$ 就说明还存在另一块不同的内部布。

---

最终判定逻辑

综合两类结构，对于每个询问 $[S,T]$，只需要判断：

if (Joint(S, T) || Exact(S, T)) {
    ans = true;
} else {
    ans = false;
}

其中：

• Joint(S,T) 判断是否存在左右拼接方案；
• Exact(S,T) 判断是否存在完整区间 $[S,T]$，并且内部区间数量大于 $1$。

对应代码中，Exact 函数写作：

bool Exact(int l, int r, const Fenwick &bit) {
    if (!exact_LR.count(Key(l, r))) {
        return false;
    }
    return bit.query(r) > 1;
}

完整处理过程如下：

void Solve() {
    Fenwick bit(n);
    int cur_L = n;

    for (Query qy : Q) {
        while (cur_L >= qy.l) {
            for (int r : L[cur_L]) {
                bit.add(r);
            }
            cur_L--;
        }

        if (Joint(qy.l, qy.r) || Exact(qy.l, qy.r, bit)) {
            ans[qy.id] = true;
        }
    }
}

由于询问被重新排序过，所以需要保留每个询问的原始编号 id，最后再按原顺序输出答案。

---

复杂度分析

预处理 L 和 R 时，需要对各个端点分组内的数组排序。

所有数组中的元素总数为 $M$，因此排序总复杂度可以看作：

$$O(M\log M)$$

对于每个询问，左右拼接部分会进行两次二分查询，复杂度为：

$$O(\log M)$$

总计：

$$O(Q\log M)$$

离线树状数组部分中，每块布只会被加入一次，每个询问只会查询一次，因此复杂度为：

$$O((M+Q)\log N)$$

所以总时间复杂度为：

$$O((M+Q)\log N)$$

空间复杂度方面，需要存储所有区间、所有询问、端点分组、树状数组以及答案数组，因此为：

$$O(N+M+Q)$$

本题数据范围为：

$$N,M,Q\le 2\times 10^5$$

可以通过。

---

提交记录及 AC 代码

提交记录如下。

点击展开/折叠 最终 AC 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr ll maxn = 2e5 + 5;

struct Query {
    int l, r, id;
};

struct Fenwick {
    int n;
    vector<int> c;

    Fenwick(int _n) : n(_n), c(n + 1, 0) {
    }

    static int lowbit(int x) {
        return x & -x;
    }

    void add(int x) {
        for (int i = x; i <= n; i += lowbit(i)) {
            c[i]++;
        }
    }

    [[nodiscard]] int query(int x) const {
        int sum = 0;
        for (int i = x; i; i -= lowbit(i)) {
            sum += c[i];
        }
        return sum;
    }
};

int n, m, q;
bool ans[maxn];
vector<int> L[maxn], R[maxn];
vector<Query> Q;
unordered_set<ll> exact_LR;

void init() {
    for (int i = 1; i <= n; i++) {
        if (!L[i].empty()) {
            sort(L[i].begin(), L[i].end());
        }
        if (!R[i].empty()) {
            sort(R[i].begin(), R[i].end());
        }
    }
    sort(Q.begin(), Q.end(), [](const Query &a, const Query &b) {
        return a.l > b.l;
    });
}

ll Key(int l, int r) {
    return 1ll * l * maxn + r;
}

bool Joint(int l, int r) {
    if (L[l].empty() || R[r].empty()) {
        return false;
    }
    auto it_r = lower_bound(L[l].begin(), L[l].end(), r);
    auto it_l = upper_bound(R[r].begin(), R[r].end(), l);
    if (it_r == L[l].begin() || it_l == R[r].end()) {
        return false;
    }
    --it_r;
    return *it_r + 1 >= *it_l;
}

bool Exact(int l, int r, const Fenwick &bit) {
    if (!exact_LR.count(Key(l, r))) {
        return false;
    }
    return bit.query(r) > 1;
}

void Solve() {
    Fenwick bit(n);
    int cur_L = n;
    for (Query qy: Q) {
        while (cur_L >= qy.l) {
            for (int r: L[cur_L]) {
                bit.add(r);
            }
            cur_L--;
        }
        if (Joint(qy.l, qy.r) || Exact(qy.l, qy.r, bit)) {
            ans[qy.id] = true;
        }
    }
}

void printANS() {
    for (int i = 1; i <= q; i++) {
        cout << (ans[i] ? "Yes\n" : "No\n");
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        L[l].push_back(r);
        R[r].push_back(l);
        exact_LR.insert(Key(l, r));
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int s, t;
        cin >> s >> t;
        Q.push_back({s, t, i});
    }
    init();
    Solve();
    printANS();
    return 0;
}

---

结语

这题的关键不在树状数组模板本身，而在于先把合法覆盖结构拆清楚。

“两块布的并集恰好为 $[S,T]$” 可以拆成：

• 左右拼接；
• 完整区间加内部区间。

前者用端点分组与二分处理；后者转化为：

$$L_i\ge S,\quad R_i\le T$$

的二维偏序统计，再用离线树状数组解决。

这类区间题给我的启发是：先完成结构抽象，再选择数据结构。只要合法方案被拆得足够清楚，后续的二分、树状数组与离线处理都会变得自然很多。