H. La Vaca Saturno Saturnita - 题解

比赛与标签

比赛: Codeforces Round 1017 (Div. 4) 标签: binary search, brute force, math, number theory 难度: *1900

主人，这是什么任务喵？

Nya~ 这道题是说，有一个神秘的函数 f(k, a, l, r)，它会根据一个数组 a 和一个数字 k 来计算一个结果。

具体来说，函数会从数组 a 的第 l 个元素开始，一直遍历到第 r 个元素。对于每一个元素 a[i]，它会不停地用 k去除以 a[i]，直到 k 不能再被 a[i] 整除为止。做完这个除法操作后，它会把当前 k 的值加到总答案 ans 里。

最关键的地方在于，k 的值是会变化的！处理完 a[i] 后，变小的 k 会被带到下一个位置 a[i+1] 继续计算。

我们的任务就是，对于每一个给出的查询 (k, l, r)，算出这个 f(k, a, l, r) 的最终值是多少~

猫猫的思考时间喵~

如果直接按照题目描述的方法去模拟，对于每个查询都从 l 遍历到 r，那复杂度会是 O(q * n * logk)。看到 n 和 q 的大小，就知道这样肯定会超时的说！(>ω<) 我们需要更聪明的办法！

关键的突破口在于观察 k 是如何变化的。k 的值只在 a[i] 能整除它的时候才会改变。一个很重要的推论是：如果 a[i] 连初始的 k 都不能整除，那在后续的计算中（k只会变小或不变），它也绝对不可能整除 k 了。

所以，我们只需要关注那些 a[i] 是初始 k 的约数的位置 i。这些位置才是可能让 k 发生变化的“关键点”或者说“事件点”！

对于那些 a[i] 不是初始 k 的约数的普通位置，k 的值是不会变的。这意味着，在两个相邻的“事件点”之间，所有普通位置对答案的贡献都是相同的，也就是当时 k 的值。

于是，一个高效的解法就诞生了喵！

1. 预处理喵~: 为了快速找到某个值在数组 a 中出现的所有位置，我们可以建一个“倒排索引”。简单来说，就是用一个 vector<vector<int>>，v[x] 存储了所有值为 x 的元素在数组 a 中的下标。这样 v[x] 就是一个有序的下标列表啦。

2. 处理询问呐: 对于每个查询 (k, l, r)：

   • 找到所有约数: 先把初始 k 的所有约数都找出来。这个用 O(sqrt(k)) 的方法就可以轻松搞定。
   • 定位事件点: 遍历 k 的每个约数 d。利用我们预处理好的倒排索引 v[d]，通过二分查找 (lower_bound) 快速找到在 [l, r] 范围内的第一个 a[i] = d 的位置 i。把所有这样的 (i, d) 作为事件点存起来。
   • 排序并处理: 将所有找到的事件点按照下标 i 从小到大排序。这样我们就能按顺序处理了。
   • 分段计算: 我们维护一个变量 last，表示上一个处理过的事件点的下标。从 l-1 开始，遍历所有事件点 (idx, d)：
     • last 和 idx 之间的区间 (last, idx) 都是普通点，k 的值没有变。这部分的贡献就是 k * (idx - last - 1)。
     • 在 idx 这个事件点，我们用 d 去更新 k（while(k % d == 0) k /= d;），然后把新的 k 值加到答案里。
     • 更新 last = idx。
   • 收尾工作: 遍历完所有事件点后，别忘了从 last 到 r 还有一段区间呢！这部分的贡献是 k * (r - last)。

通过这种“事件驱动”的思路，我们把 O(n) 的遍历优化成了只处理少数几个关键点，问题就迎刃而解啦！

Code Time! 喵~

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// a[i] 和 k 的最大值是 100000，我们预处理的数组开到这个大小就够啦
const int MAX_VAL = 100000;

void solve(vector<vector<int>>& v) {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        // 建立倒排索引：v[val] 存储了所有 a[i] == val 的下标 i
        if (a[i] >= 2 && a[i] <= MAX_VAL) {
            v[a[i]].push_back(i);
        }
    }

    while (q--) {
        long long k;
        int l, r;
        cin >> k >> l >> r;

        // 1. 找出初始 k 的所有约数
        vector<long long> divs;
        for (long long i = 1; i * i <= k; i++) {
            if (k % i == 0) {
                divs.push_back(i);
                if (i != k / i) {
                    divs.push_back(k / i);
                }
            }
        }

        // 2. 找到所有在 [l, r] 范围内的事件点 (index, divisor)
        vector<pair<int, int>> events;
        for (long long d_val : divs) {
            if (d_val < 2 || d_val > MAX_VAL) continue; // a[i] >= 2，所以约数1没用
            int d = static_cast<int>(d_val);

            if (v[d].empty()) continue; // 如果这个约数在数组 a 中从未出现过，就跳过

            // 使用二分查找，找到第一个大于等于 l 的下标
            auto it = lower_bound(v[d].begin(), v[d].end(), l);

            // 如果找到了，并且这个下标在 r 范围内，就是一个有效的事件点
            if (it != v[d].end() && *it <= r) {
                events.push_back({*it, d});
            }
        }

        // 3. 将事件点按坐标排序，确保我们按从 l 到 r 的顺序处理
        sort(events.begin(), events.end());

        long long ans = 0;
        int last = l - 1; // last 记录上一个处理过的事件点下标

        // 4. 遍历事件点，分段计算贡献
        for (auto event : events) {
            int idx = event.first;
            int d = event.second;

            // 计算从上个事件点到当前事件点之间的 "平稳" 区间的贡献
            // 这里的 k 还是上一个事件点处理完之后的值
            if (last + 1 < idx) {
                ans += k * (idx - last - 1);
            }

            // 在当前事件点 idx，更新 k 的值
            while (k % d == 0) {
                k /= d;
            }
            
            // 加上当前事件点处理后的 k 值
            ans += k;
            last = idx; // 更新 last
        }

        // 5. 处理最后一个事件点到 r 的区间的贡献
        if (last < r) {
            ans += k * (r - last);
        }

        cout << ans << '\n';
    }

    // 多组测试用例，需要清空倒排索引以备下次使用，这样比每次重新创建更高效
    for (int i = 0; i <= MAX_VAL; i++) {
        if (!v[i].empty()) {
            v[i].clear();
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<vector<int>> v(MAX_VAL + 1);
    int t;
    cin >> t;
    while (t--) {
        solve(v);
    }

    return 0;
}

How Fast Is This Cat? 喵~

• 时间复杂度: O(ΣN + ΣQ * (sqrt(K_max) + D * (logN + logD + logK_max))) 的说。
  • ΣN 是所有测试用例 n 的总和，用于构建倒排索引。
  • 对于每个查询，sqrt(K_max) 用于找约数。D 是 k 的最大约数个数（对于 10^5 以内的数，D 很小，远小于150）。logN 是二分查找的开销，logD 是排序事件的开销，logK_max 是 while 除法循环的开销。总之，非常快！
• 空间复杂度: O(ΣN + K_max) 的说。
  • O(ΣN) 主要来自倒排索引 v。因为所有测试用例的 n 加起来有上限，所以空间是可控的。K_max 是为了开 v 数组。查询中临时变量的空间可以忽略不计。

知识点与总结喵！

这道题真是一次有趣的冒险呢！它教会了我们：

1. 事件排序 (Event Sorting): 当处理一个区间，并且区间内的值只在少数几个“关键点”发生变化时，把这些关键点找出来，按位置排序，然后分段处理，是一种非常强大的优化技巧！
2. 预处理与倒排索引: “预先计算，空间换时间”是算法竞赛中的王道喵！建立倒排索引，可以把“在整个数组里找某个值”的操作优化到 O(logN)，非常高效。
3. 数论基础: 快速分解质因数、找约数，这些是解决很多数学和组合问题的基本功，要熟练掌握哦。
4. 二分查找 (lower_bound): std::lower_bound 是 C++ STL 的一把利器，在有序序列中查找元素时超级好用，一定要和它成为好朋友！

总之，遇到看似要暴力循环的题目，先别急着动手，静下心来想一想，是不是有什么性质可以利用，是不是可以把 O(N) 的扫描变成对少数几个“事件点”的处理。这样思考，就能找到通往AC的捷径啦！主人下次也要加油哦！(๑•̀ㅂ•́)و✧