F. Ant colony - 题解

比赛与标签

比赛: Codeforces Round 271 (Div. 2) 标签: data structures, math, number theory 难度: *2100

小猫咪的饥饿游戏喵~

Mole大人肚子饿啦，要看一群小蚂蚁打架来找点乐子，真是个坏心眼的鼹鼠呐！

事情是这样的：有一排 n 只蚂蚁，每只都有一个自己的力量值 s。Mole大人会选定一个区间 [l, r]，然后这个区间里的每一对蚂蚁都要打一架。

打架的规则很简单：如果蚂蚁 i 的力量 s_i 能够整除蚂蚁 j 的力量 s_j，那么蚂蚁 i 就能从 j 身上拿到1分。

在一场范围为 [l, r] 的游戏中，总共有 r - l + 1 只蚂蚁。如果一只蚂蚁在它参与的所有 r - l 场战斗中都取得了胜利（也就是拿到了 r - l 分），那它就会被光荣释放！剩下的蚂蚁嘛...就变成Mole大人的晚餐啦（呜...好可怜）。

我们的任务就是，对于Mole大人给出的 t 个查询区间 [l, r]，计算出每个区间里有多少只蚂蚁会被吃掉。

胜利的秘密喵！

要怎么才能不被吃掉，成功被释放呢？我们来分析一下条件喵！

一只在区间 [l, r] 内的蚂蚁 i 要被释放，它的得分必须是 r - l。这意味着，对于区间内所有其他的蚂蚁 j (其中 j ≠ i)，s_i 都必须能整除 s_j。当然啦，s_i 也能整除自己，所以这个条件可以简化为：s_i 必须能整除区间 [l, r] 内的每一个 s_j。

这是一个非常非常强的条件呐！你想想看：

1. 如果 s_i 能整除区间内所有的数，那它一定是这个区间所有数的一个公约数。
2. 同时，s_i 要想整除别的数，它自己肯定不能比别的大对吧？（除非是负数，但这里的力量都是正数）。所以，s_i 必须是区间内最小的那个数。如果还有比它更小的数，它就不可能整除那个更小的数了。

把这两点合起来，一个能被释放的蚂蚁，它的力量 s_i 必须同时是区间的最小值和区间的公约数。

等一下！一个数集的最大公约数（GCD）有一个性质：它一定小于或等于这个数集中的任何一个数。所以，如果 s_i 是区间 [l, r] 所有力量的公约数，那么 s_i 必然小于或等于区间的 GCD(s_l, ..., s_r)。而 GCD(s_l, ..., s_r) 又必然小于或等于区间的最小值 min(s_l, ..., s_r)。

所以，如果一只蚂蚁 i 能被释放，它的力量 s_i 必须是区间的最小值。同时，这个最小值还必须能整除区间里所有的数，这意味着它就是区间的 GCD！

当当当当~ 结论就出来啦！ 一只蚂蚁能被释放的充要条件是：它的力量 s_i 恰好等于区间 [l, r] 所有力量的最小值，并且也等于这个区间的最大公约数（GCD）。

所以，我们的解题策略就清晰了喵：

1. 对于每个查询 [l, r]，我们先求出这个区间的最小值 min_val 和最大公约数 gcd_val。
2. 如果 min_val 不等于 gcd_val，说明没有任何一只蚂蚁的力量能满足条件，所以被释放的蚂蚁数量是 0。
3. 如果 min_val 等于 gcd_val，那么所有力量值等于 min_val (也就是 gcd_val) 的蚂蚁都会被释放！我们只需要数一数在区间 [l, r] 内，有多少只蚂蚁的力量值是这个数就行啦。
4. 最后，用区间总蚂蚁数 (r - l + 1) 减去被释放的蚂蚁数，就是被吃掉的数量啦！

那么问题来了，怎么快速地计算区间最小值、区间GCD和区间内特定值的数量呢？

• 区间最小值/GCD：因为蚂蚁的力量值是固定的，这是个静态区间查询问题。稀疏表（Sparse Table, ST） 就是为此而生的！它可以在 O(N log N) 预处理后，以 O(1) 的速度回答每个查询，超级快的说！我们可以建一个ST，每个节点同时存下区间的最小值和GCD。
• 区间内特定值的数量：我们可以预处理一下，用一个 std::map<int, std::vector<int>> 来记录每种力量值都出现在了哪些位置（下标）。当我们要找某个值在区间 [l, r] 的数量时，先在map里找到这个值对应的下标列表，然后用二分查找（比如 std::lower_bound 和 std::upper_bound）来快速定位 l 和 r 的边界，就能算出数量了！

好耶！思路清晰，可以开始写代码啦！

亮出爪爪写代码！

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

// 使用快速I/O，让程序跑得飞快喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

const int MAXN = 100005;
const int LOGN = 18; // ceil(log2(100005)) 约等于 16.6, 18 足够安全了
int s[MAXN];
int n;

// 稀疏表的节点，同时存储区间的最小值和最大公约数
struct Node {
    int min_val;
    int gcd_val;
};

Node st[MAXN][LOGN];
int log_table[MAXN];

// 合并两个节点的信息
Node merge(const Node& a, const Node& b) {
    return {std::min(a.min_val, b.min_val), std::gcd(a.gcd_val, b.gcd_val)};
}

// O(N log N) 构建稀疏表
void build_sparse_table() {
    // 初始化，每个长度为1的区间，最小值和GCD都是它自己
    for (int i = 0; i < n; ++i) {
        st[i][0] = {s[i], s[i]};
    }
    // 倍增思想，从小区间合并成大区间
    for (int j = 1; j < LOGN; ++j) {
        for (int i = 0; i + (1 << j) <= n; ++i) {
            st[i][j] = merge(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// O(1) 查询区间 [l, r] 的信息
Node query_sparse_table(int l, int r) { // inclusive, 0-indexed
    int len = r - l + 1;
    int k = log_table[len]; // 预计算的log2值
    // 查询被拆分成两个可能重叠的区间，但不影响min和gcd的正确性
    return merge(st[l][k], st[r - (1 << k) + 1][k]);
}

// 预计算log2的值，避免每次查询都调用log函数
void precompute_logs() {
    log_table[1] = 0;
    for (int i = 2; i < MAXN; ++i) {
        log_table[i] = log_table[i / 2] + 1;
    }
}

// 用map记录每种力量值出现的所有位置（下标）
std::map<int, std::vector<int>> positions;

// O(N log N) 或 O(N) 平均，构建位置映射表
void build_positions_map() {
    for (int i = 0; i < n; ++i) {
        positions[s[i]].push_back(i);
    }
}

int main() {
    fast_io();

    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::cin >> s[i];
    }

    // 预处理阶段
    precompute_logs();
    build_sparse_table();
    build_positions_map();

    int t;
    std::cin >> t;
    while (t--) {
        int l, r;
        std::cin >> l >> r;
        --l; --r; // 题目是1-indexed，我们转成0-indexed好处理喵~

        // 1. 用ST查询区间的min和gcd
        Node result = query_sparse_table(l, r);
        
        int total_ants = r - l + 1;
        int freed_count = 0;

        // 2. 检查min和gcd是否相等
        if (result.min_val == result.gcd_val) {
            int val_to_find = result.min_val;
            auto it = positions.find(val_to_find);
            
            // 3. 如果相等，就去查这个值在区间里出现了多少次
            if (it != positions.end()) {
                const auto& vec = it->second;
                // 用二分查找快速统计在 [l, r] 范围内的下标数量
                auto lower = std::lower_bound(vec.begin(), vec.end(), l);
                auto upper = std::upper_bound(vec.begin(), vec.end(), r);
                freed_count = std::distance(lower, upper);
            }
        }
        
        // 4. 计算被吃掉的蚂蚁数量
        int eaten_ants = total_ants - freed_count;
        std::cout << eaten_ants << "\n";
    }

    return 0;
}

跑得快不快呀？

• 时间复杂度: O(N log N + T log N) 的说

  • 预处理阶段：构建稀疏表是 O(N log N)，构建位置映射表最坏是 O(N log N)。所以总预处理是 O(N log N)。
  • 查询阶段：每个查询 t 次，ST查询是 O(1)，map查找是 O(log N)，在vector上二分查找也是 O(log N)。所以每次查询是 O(log N)。
  • 总时间就是 O(N log N + T log N)，对于 N 和 T 都是 10^5 的数据量来说，完全没问题！

• 空间复杂度: O(N log N) 的说

  • 稀疏表 st 的大小是 N * log N，这是空间的大头。
  • 位置映射表 positions 最多存 N 个下标，所以是 O(N)。
  • log_table 也是 O(N)。
  • 所以总空间复杂度由稀疏表决定，是 O(N log N)。

小猫咪的知识宝库

这道题真有趣，对吧！它把数论和数据结构巧妙地结合在了一起，我们来总结一下学到了什么吧~

1. 核心思想转换: 这是解题最关键的一步！把"能整除区间内所有其他数"这个复杂的逻辑，通过分析，转换成了"力量值等于区间的最小值，且等于区间的GCD"这个等价且易于计算的条件。很多难题的突破口都在于这种观察和转换哦！

2. 稀疏表 (Sparse Table): 再次证明了ST是处理静态区间查询问题（如RMQ、Range Sum、Range GCD）的强大工具。它的 O(1) 查询速度真的太香啦！

3. 预处理与查询: 这是一种非常经典的算法设计模式。通过前期的预处理，将大量计算工作分摊，从而使得每一次的独立查询都能非常高效。

4. 二分查找的应用: std::lower_bound 和 std::upper_bound 是C++ STL的利器，它们能在有序容器上飞快地找到元素的边界，是实现区间计数的标准姿势。

希望这次的讲解对你有帮助喵~ 如果还有不懂的地方，随时可以再来问我哦！一起加油，成为更厉害的算法大师吧！(ฅ'ω'ฅ)