E. Induced Subgraph Queries - 题解

比赛与标签

比赛: Codeforces Round 1040 (Div. 1) 标签: data structures, sortings 难度: (无评分信息)

喵哈！题目要我们做什么呀？

主人，你好喵~！这道题看起来弯弯绕绕的，但别担心，让本喵来给你梳理一下，很快就能明白啦！

简单来说，我们有一个图和一大堆查询。每个查询会给我们三个数字 l, r, k。

圈定一个范围: 首先，我们要关注所有编号在 l 到 r 之间的节点，我们把这个节点集合叫做 V'。
生成子图: 接着，我们从原图中拿出 V' 里的所有节点，以及所有两个端点都在 V' 里的边，组成一个新的图，也就是题目里说的“诱导子图” G[V']。
计算异或和: 对于 G[V'] 中的每一个节点 u，我们要找到它在这个子图里的所有邻居 v，然后把这些邻居 v 的编号全部做一次按位异或（XOR）运算。如果一个节点在子图里没有邻居，那它的异或和就是 0 啦，喵~
寻找第k小: 我们对 V' 里的每个节点都计算出这样一个异或和，就会得到一堆数字。最后一步，就是把这些数字从小到大排个序，找出第 k 小的那个值作为答案。

总而言之，就是在一个动态变化的子图里，计算一堆异或和，然后找第 k 小值。是不是听起来就很有挑战性呀？别怕，跟着本喵的思路走，保证没问题！

猫猫的思考时间！解题思路大揭秘喵~

看到这种在固定区间 [l, r] 上进行查询，而且题目没有要求我们必须立刻回答（也就是“离线”），本喵的DNA就动了！这不就是莫队算法的经典应用场景嘛！

为什么是莫队算法？

莫队算法是一种优雅的暴力，它通过巧妙地对查询进行排序，来优化区间指针 l 和 r 的移动次数，从而把整体复杂度降下来。对于这道题，我们可以在 [l, r] 区间上移动指针，动态地维护节点集合 V' 以及其中每个节点的异或和。

普通莫队够用吗？

普通的莫队算法假设我们 add (添加一个点) 和 remove (删除一个点) 的操作是 O(1) 的。但在这里，当我们添加一个点 p 到区间里时，我们需要更新它所有邻居的异或和。如果点 p 的度是 deg(p)，这个操作的开销就是 O(deg(p))，这可不是 O(1) 呀！如果图里有个超级节点，那复杂度不就爆炸了嘛？

更聪明的莫队——带权莫队！

为了解决这个问题，我们要用一个更强大的版本——带权莫队！

核心思想是：既然 add/remove 一个点 p 的代价和它的度 deg(p) 有关，那我们干脆在分块的时候就把这个代价考虑进去！

我们不再按照点的编号 1, 2, ..., n 来分块，而是根据“累计代价”来分块。我们给每个点 i 定义一个权重，就定为 deg(i) + 1 好了（+1 是为了算上对点 i 自身的操作）。然后我们计算一个权重前缀和数组 w，其中 w[i] 表示从点 1 到点 i 的累计权重。

在对查询排序时，我们用来分块的关键字就不是 query.l / block_size 了，而是 w[query.l] / block_size！这样，虽然每个块里点的数量可能不同，但每个块所代表的“总操作代价”是大致相等的。这就能有效地均衡 l 指针移动带来的总开销，让算法的复杂度保持在可控范围内，喵~

如何维护异或和并查询第k小？

当我们的莫队指针 l 和 r 移动时，我们需要一个数据结构来实时维护当前区间 [l, r] 内所有节点的异或和，并且能快速回答“第k小的值是多少”的查询。

这个数据结构需要支持：

插入一个值
删除一个值
查询第k小值

这里，AC代码用了一个非常经典且高效的技巧：值域分块！我们可以开一个大数组 counts，counts[x] 记录当前异或和为 x 的节点有多少个。由于 n 最大是 1.5 * 10^5，异或和最大不会超过 2^18 - 1 (262143)。为了快速查询，我们再把这个值域（0 到 262143）分成若干个块，用一个 blocks 数组记录每个块里有多少个值。

更新 (ds_update): 插入或删除一个值 val，只需要 O(1) 时间修改 counts[val] 和 blocks[val / block_size]。
查询 (ds_query): 找第k小值时，我们先一个块一个块地跳，用 O(sqrt(V_max)) 的时间确定目标值在哪一个块里，然后再在那个块里一个一个地数，同样用 O(sqrt(V_max)) 的时间找到具体的值。

`add` 和 `remove` 的具体实现

这是整个算法最核心的部分啦，要特别小心哦！

add(p): 当我们将节点 p 加入当前区间时：
1. p 本身现在是活跃节点了。它当前的异或和 val[p]（只考虑已在区间内的邻居）需要被加入我们的值域分块数据结构中。
2. 对于 p 的每一个邻居 v，v 的异或和 val[v] 会因为 p 的加入而改变（需要异或上 p）。
3. 关键点: 如果邻居 v 本身也已经是活跃节点（即 v 也在 [l, r] 区间内），我们就必须先从数据结构中移除旧的 val[v]，更新 val[v] = val[v] ^ p，再把新的 val[v] 加回数据结构。如果 v 不在区间内，我们只更新 val[v] 就好，因为它本来就不在我们的统计范围内。
remove(p): 逻辑和 add(p) 完全相反，做一个对称的操作就好啦！

把这些部分组合起来，我们就得到了一个完整又高效的解决方案，喵~

喵喵代码教室~

下面就是AC代码啦，本喵在关键的地方都加上了详细的注释，帮助主人更好地理解哦！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

// 常量定义
constexpr int MAX_XOR_VAL = 1 << 18; // 异或值的最大范围，n <= 1.5e5，所以最大异或和 < 2^18
constexpr int DS_BLOCK_SIZE = 512;   // 值域分块的块大小，约等于 sqrt(MAX_XOR_VAL)

// 值域分块数据结构，用于查询第k小
std::vector<int> counts; // counts[i] 表示异或值为 i 的节点数量
std::vector<int> blocks; // blocks[j] 表示第 j 个块内节点的总数量

// 更新：将值 val 的计数增加 delta
void ds_update(int val, int delta) {
    counts[val] += delta;
    blocks[val / DS_BLOCK_SIZE] += delta;
}

// 查询：找到第 k 小的值
int ds_query(int k) {
    int block_idx = 0;
    // 1. 快速跳块，找到 k 所在的块
    while (k > blocks[block_idx]) {
        k -= blocks[block_idx];
        block_idx++;
    }
    // 2. 在块内线性扫描，找到具体的值
    int val_idx = block_idx * DS_BLOCK_SIZE;
    while (k > counts[val_idx]) {
        k -= counts[val_idx];
        val_idx++;
    }
    return val_idx;
}

// 莫队算法的查询结构体
struct Query {
    int l, r, k, id;
    long long l_w_block; // 带权重的左端点块编号
};

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> adj(n + 1);
    std::vector<int> degree(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

    // 计算带权莫队的权重前缀和
    std::vector<long long> w(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        w[i] = w[i - 1] + degree[i] + 1;
    }

    int q;
    std::cin >> q;
    std::vector<Query> queries(q);
    const int MO_BLOCK_SIZE = 800; // 莫队分块大小，这是一个经验值

    for (int i = 0; i < q; ++i) {
        std::cin >> queries[i].l >> queries[i].r >> queries[i].k;
        queries[i].id = i;
        // 使用权重前缀和来计算块编号
        queries[i].l_w_block = w[queries[i].l] / MO_BLOCK_SIZE;
    }

    // 莫队排序，带奇偶性优化
    std::sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
        if (a.l_w_block != b.l_w_block) {
            return a.l_w_block < b.l_w_block;
        }
        if (a.l_w_block % 2) {
            return a.r < b.r;
        }
        return a.r > b.r;
    });

    std::vector<int> ans(q);
    std::vector<int> val(n + 1, 0); // val[i] 存储节点 i 当前的异或和
    std::vector<bool> active(n + 1, false); // active[i] 标记节点 i 是否在当前 [l,r] 区间内
    counts.assign(MAX_XOR_VAL, 0);
    blocks.assign(MAX_XOR_VAL / DS_BLOCK_SIZE + 1, 0);

    // 核心辅助函数：当节点 u 的邻居 p 状态改变时，更新 u 的异或和
    auto change_val = [&](int u, int p) {
        if (active[u]) { // 如果 u 本身是活跃的
            ds_update(val[u], -1); // 先从数据结构中移除旧值
        }
        val[u] ^= p; // 更新 u 的异或和
        if (active[u]) { // 如果 u 本身是活跃的
            ds_update(val[u], 1); // 再把新值加回去
        }
    };

    // 将节点 p 添加到当前集合
    auto add = [&](int p) {
        active[p] = true; // 标记为活跃
        ds_update(val[p], 1); // 将它当前的异或和加入统计
        for (int v : adj[p]) { // 遍历所有邻居
            change_val(v, p); // 更新邻居的异或和
        }
    };

    // 从当前集合中移除节点 p
    auto remove = [&](int p) {
        active[p] = false; // 标记为不活跃
        ds_update(val[p], -1); // 从统计中移除它的异或和
        for (int v : adj[p]) { // 遍历所有邻居
            change_val(v, p); // 恢复邻居的异或和（再次异或p即可）
        }
    };

    int current_l = 1;
    int current_r = 0;

    // 莫队算法主循环
    for (const auto& query : queries) {
        int l = query.l, r = query.r, k = query.k;
        // 扩展区间
        while (current_l > l) {
            current_l--;
            add(current_l);
        }
        while (current_r < r) {
            current_r++;
            add(current_r);
        }
        // 缩减区间
        while (current_l < l) {
            remove(current_l);
            current_l++;
        }
        while (current_r > r) {
            remove(current_r);
            current_r--;
        }
        // 所有指针移动到位后，查询答案
        ans[query.id] = ds_query(k);
    }

    for (int i = 0; i < q; ++i) {
        std::cout << ans[i] << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

时空复杂度分析喵

时间复杂度: O((N+M) * sqrt(N+M) + Q * sqrt(V_max)) 的说。让我来解释一下喵~ 设 N, M, Q 分别是点数、边数和查询数，V_max 是最大异或值。
1. 查询排序: O(Q log Q)。
2. 莫队指针移动: 带权莫队通过巧妙的分块，保证了指针移动的总代价。总权重 W = O(N+M)。设块大小为 B，r 指针移动的总代价是 O(W)。l 指针在每个块内移动，总代价是 O(Q * B)。取 B 约等于 W/sqrt(Q)，总代价约为 O(W * sqrt(Q))。考虑到 N, M, Q 在同一数量级，可以粗略记为 O((N+M) * sqrt(N+M))。
3. 查询第k小: 每次查询的代价是 O(sqrt(V_max))。总共 Q 次查询，所以是 O(Q * sqrt(V_max))。结合起来，总时间复杂度就是 O((N+M) * sqrt(N+M) + Q * sqrt(V_max))。对于本题的数据范围，这个复杂度是可以通过的！
空间复杂度: O(N + M + Q + V_max) 的说。
1. 邻接表 adj 占 O(N + M)。
2. val, active, degree, w 等辅助数组占 O(N)。
3. 存储查询的 queries 数组占 O(Q)。
4. 值域分块的 counts 和 blocks 数组占 O(V_max)。所以总空间复杂度是 O(N + M + Q + V_max)。

本喵的小总结~

这道题真是一次算法的盛宴呀！它完美地结合了两种强大的技巧：

核心算法: 带权莫队！这告诉我们，当莫队算法中 add/remove 操作的代价不恒定时，我们可以通过对代价分块来“驯服”它，这是一种非常灵活和强大的思想，值得我们牢牢记住喵！
数据结构: 值域分块！在需要频繁进行插入、删除和排名查询时，如果值域范围不大，它是一个实现简单、效果出色的选择。比写一棵复杂的平衡树要轻松多啦！
解题思想: 离线处理是解决许多区间问题的金钥匙。当你发现一个问题在线做很困难时，不妨想一想，能不能把所有查询收集起来，用更聪明的顺序一次性处理掉呢？

希望本喵的讲解对你有帮助哦！这道题虽然有点难，但只要一步步拆解，就能发现其中的奥秘。继续加油，你一定可以成为算法大师的，喵~！

E. Induced Subgraph Queries - 题解 ​

比赛与标签 ​

喵哈！题目要我们做什么呀？ ​

猫猫的思考时间！解题思路大揭秘喵~ ​

为什么是莫队算法？ ​

普通莫队够用吗？ ​

更聪明的莫队——带权莫队！ ​

如何维护异或和并查询第k小？ ​

add 和 remove 的具体实现 ​

喵喵代码教室~ ​

时空复杂度分析喵 ​

本喵的小总结~ ​