Moe's CF Life

Appearance

F. Range Update Point Query - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 849 (Div. 4) 标签: binary search, brute force, data structures 难度: *1500

题目大意喵~ ​

主人，这道题是这样子的：

我们有一个数组 a，包含 n 个整数。接下来有 q 次操作，操作分为两种类型：

  1. 范围更新 (Type 1): 给定一个区间 [l, r]，我们需要把这个区间里每一个数字 a[i] 都变成它自己的各位数字之和。比如说，420 就会变成 4+2+0=6，69 就会变成 6+9=15 呐。
  2. 单点查询 (Type 2): 给定一个位置 x，我们需要回答此时 a[x] 的值是多少。

我们需要正确地处理所有操作，并对每个查询输出答案。很简单直观的要求，对吧？

解题思路大揭秘！ ​

嘿嘿，看到范围更新，很多小伙伴可能第一反应是线段树或者树状数组。但是，这里的更新操作是“求各位数字之和”，这个操作非常特殊，不是简单的加减，所以常规的线段树懒标记（lazy propagation）好像不太好用呢，喵~

如果我们对每个范围更新操作，都老老实实地写一个循环从 l 到 r 去修改，会发生什么呢？ for (int i = l; i <= r; ++i) a[i] = digit_sum(a[i]); 在最坏的情况下，l=1, r=n，一次更新就要 O(n) 的时间，q 次查询下来，总时间复杂度就是 O(q * n)，这对于 n, q 高达 2 * 10^5 的数据量来说，肯定是会超时（Time Limit Exceeded）的啦！

那么，一定有什么我们没发现的奥秘！让我们来仔细研究一下这个“各位数字之和”操作吧！ 我们来随便找几个数字试试看：

  • 12345 -> 1+2+3+4+5 = 15
  • 15 -> 1+5 = 6
  • 6 -> 6 (咦，不变了！)

再来一个大一点的：

  • 999,999,999 (一个很大的数) -> 9 * 9 = 81
  • 81 -> 8+1 = 9
  • 9 -> 9 (又不变了！)

发现了没有？一个数字，在经过若干次“各位数字之和”的操作后，会很快地变成一个个位数（小于10的数）。而一旦一个数变成了个位数，它再进行这个操作，值是不会改变的！digit_sum(x) = x for x < 10。

这个发现太重要了！这意味着，对于数组中的任何一个元素，我们其实只需要对它进行有限次的更新。一旦它变成了个位数，我们就可以永远地忽略它了，因为它已经“稳定”下来，不会再变了，喵~

所以，我们的优化思路就来啦：我们只对那些还没有变成个位数的数字进行更新！

为了实现这个想法，我们需要一个能够高效完成以下任务的数据结构：

  1. 存储所有值 a[i] >= 10 的元素的下标 i。
  2. 对于一个查询区间 [l, r]，能够快速地找出所有在这个区间内的、需要更新的下标。

std::set 就是一个非常棒的选择！我们可以创建一个 set，里面存放所有当前值大于等于10的元素的下标。

当遇到一个 1 l r 的更新操作时，我们就不再傻傻地遍历 i from l to r 了。取而代之的是：

  1. 我们利用 set 的 lower_bound(l) 方法，快速定位到第一个大于等于 l 的、需要更新的下标。
  2. 从这个位置开始，我们向后遍历 set，只要当前下标还在 r 的范围内，我们就对它进行更新。
  3. 更新 a[idx] 的值之后，检查一下新的 a[idx] 是否小于10。如果小于10了，说明这个位置的数已经“稳定”，我们就可以把它从 set 中移除，下次就再也不会打扰它啦！

因为每个元素最多只会被更新几次（对于 10^9 以内的数，最多也就两三次），然后就会从 set 中被永久移除。所以，总的更新次数是非常有限的。这样一来，时间复杂度就大大降低了，完全可以通过此题！

代码实现时间~ ​

下面就是实现这个思路的AC代码啦，猫娘已经加上了详细的注释，希望能帮到你理解哦！

cpp
#include <iostream>
#include <vector>
#include <set>

// 计算一个数的各位数字之和的函数
long long digit_sum(long long x) {
    long long s = 0;
    while (x > 0) {
        s += x % 10;
        x /= 10;
    }
    return s;
}

void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> a(n + 1);
    // non_stable 这个 set 用来存储所有值大于等于10的元素的下标
    // 这样我们就可以只对这些“不稳定”的数进行操作，喵~
    std::set<int> non_stable; 
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        if (a[i] >= 10) {
            non_stable.insert(i);
        }
    }

    while (q--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int l, r;
            std::cin >> l >> r;
            // 使用 lower_bound 快速找到第一个需要更新的下标
            // it 是一个指向 set 中元素的迭代器
            auto it = non_stable.lower_bound(l);
            
            // 用一个临时 vector 存储那些操作后变成个位数的下标
            // 因为在遍历 set 的时候直接删除元素是不安全的说
            std::vector<int> to_erase;
            
            // 遍历所有在 [l, r] 区间内的、需要更新的下标
            while (it != non_stable.end() && *it <= r) {
                int idx = *it;
                a[idx] = digit_sum(a[idx]);
                // 如果更新后小于10，就把它标记为待删除
                if (a[idx] < 10) {
                    to_erase.push_back(idx);
                }
                it++; // 继续处理下一个
            }
            
            // 统一删除那些已经“稳定”的下标
            for (int idx : to_erase) {
                non_stable.erase(idx);
            }
        } else { // op == 2
            int x;
            std::cin >> x;
            std::cout << a[x] << '\n';
        }
    }
}

int main() {
    // 优化输入输出，让程序跑得更快一点~
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

复杂度分析 ​

  • 时间复杂度: O((N+Q) * logN) 的说。
    • 每个元素 a[i] 最多只会被修改几次（一个非常小的常数C）就会变成个位数。每次修改，我们都会对它进行一次 digit_sum 操作（复杂度为 O(log a[i])）并可能伴随一次 set 的删除操作（O(logN)）。
    • 所有元素总的修改次数是 O(N * C)。所以总的修改相关的开销是 O(N * C * logN)。
    • 对于 q 次查询，每次类型1查询，我们需要一次 lower_bound（O(logN)）和若干次遍历。因为总的修改次数是有限的，所以所有类型1查询中遍历 set 的总步数也是有限的。我们可以将其均摊到每个元素上。
    • 简化来看，N 个元素初始化 set 是 O(N logN)。Q 个查询，每个查询最差可能是 O(logN)（对于 set 的查找），加上所有修改的总开销。因此，整体复杂度可以近似看作 O((N+Q)logN)。
  • 空间复杂度: O(N) 的说。
    • 我们需要一个 vector a 来存储数组，大小为 O(N)。
    • set non_stable 在最坏情况下可能存储所有 N 个下标，所以空间也是 O(N)。
    • 因此总空间复杂度是 O(N)。

猫娘的小总结 ​

这道题真是一道非常巧妙的“暴力剪枝”题呢！它的核心思想在于发现操作本身的性质：一个数经过几次digit_sum后就会收敛到个位数。

当我们发现暴力解法会超时的时候，不妨停下来，仔细分析一下题目中的操作或者条件，看看是不是有什么可以利用的性质，来帮助我们跳过那些不必要的计算。

在本题中，我们利用 std::set 成功地跳过了对那些已经“稳定”的数字的重复计算，从而将一个看似 O(N*Q) 的问题优化到了一个可以接受的复杂度。

希望这次的讲解对你有帮助哦！以后遇到类似的题目，也要记得多多观察，说不定就能发现隐藏的捷径呢！加油，你一定可以的，喵~！

Released under the MIT License.

Copyright © 2024-present Moe