G. Modular Sorting - 题解

比赛与标签

比赛: Codeforces Round 1034 (Div. 3) 标签: brute force, data structures, greedy, math, number theory, sortings 难度: *2100

喵喵，这是什么任务呀？ (题目大意)

主人你好呀~！这次的任务是这样的呐：

我们有一个模数 m 和一个非负整数数组 a。我们需要处理两种类型的查询：

1. 单点修改: 1 i x，就是把数组 a 的第 i 个元素的值改成 x 的说。
2. 可行性查询: 2 k，我们要判断一下，如果可以使用一种魔法操作 a_i := (a_i + k) mod m 任意多次，能不能把整个数组 a 变成一个非递减序列（也就是 a_1 <= a_2 <= ... <= a_n）。

要注意哦，第二种查询只是一个假设性问题，并不会真的改变数组 a 的值。只有第一种查询会永久改变数组 a 呐。

猫娘的思考时间！ (解题思路)

嘿嘿，这道题看起来有点复杂，但别怕，跟着本猫娘的思路一步步来，很快就能想明白的喵~

魔法操作的本质

首先，我们来研究一下这个神奇的魔法操作：a_i := (a_i + k) mod m。

如果我们对 a_i 多次使用这个操作，可以让它变成 (a_i + c*k) mod m，其中 c 是任意非负整数。学过数论的同学可能一眼就看出来了，这其实是说，a_i 可以变成任何一个与它模 gcd(k, m) 同余的数！

让 g = gcd(k, m)。那么 a_i 可以被变成任何一个非负整数 a'_i，只要满足 a'_i ≡ a_i (mod g)。

所以，问题就转化成了：对于给定的 k（也就是给定的 g = gcd(k, m)），我们能否找到一个新的序列 a'_1, a'_2, ..., a'_n，使得它满足下面三个条件：

1. 对于所有的 i，a'_i ≡ a_i (mod g)。
2. 对于所有的 i，0 <= a'_i < m。
3. a'_1 <= a'_2 <= ... <= a'_n（非递减）。

贪心！寻找最小的可能性

要判断是否存在这样的 a' 序列，一个很自然的想法是采用贪心策略。我们就尝试构造一个“最有可能成功”的 a' 序列，如果连它都失败了，那别的序列肯定也都不行了喵。

什么样的序列最有可能成功呢？当然是数值尽可能小的序列啦！因为我们最终的限制是 a'_n 不能超过 m-1。

为了方便处理，我们可以在数组 a 前面加一个 a_0 = 0。这样，非递减的条件就变成了 0 = a'_0 <= a'_1 <= a'_2 <= ... <= a'_n。

我们来一步步构造这个最小的 a' 序列：

• a'_0 必须是 0。
• 对于 a'_1，我们需要 a'_1 >= a'_0 = 0 并且 a'_1 ≡ a_1 (mod g)。最小的非负 a'_1 就是 a_1 mod g。
• 对于 a'_i（i > 0），我们需要它满足 a'_i >= a'_{i-1} 并且 a'_i ≡ a_i (mod g)。

这个递推关系有点麻烦，我们换个角度看。考虑相邻两项的差值 d_i = a'_i - a'_{i-1}。

• 因为序列非递减，所以 d_i >= 0。
• 因为 a'_i ≡ a_i (mod g) 和 a'_{i-1} ≡ a_{i-1} (mod g)，两式相减得到 a'_i - a'_{i-1} ≡ a_i - a_{i-1} (mod g)，也就是 d_i ≡ a_i - a_{i-1} (mod g)。

我们要让 a'_n 尽可能小，就要让从 a'_0 到 a'_n 的总增量 a'_n - a'_0 = \sum_{i=1}^{n} d_i 尽可能小。这需要我们让每个 d_i 都取到满足条件的最小值。 满足 d_i >= 0 和 d_i ≡ a_i - a_{i-1} (mod g) 的最小非负整数 d_i 是什么呢？就是 (a_i - a_{i-1}) mod g 呀！

所以，我们构造出的最小 a'_n 就是： a'_n = a'_0 + \sum_{i=1}^{n} d_i = 0 + \sum_{i=1}^{n} ((a_i - a_{i-1}) \pmod g) （这里的 a_0 是我们虚拟的 0，x mod g 表示取非负余数）。

只要这个最小的 a'_n 满足 a'_n < m，就说明存在一个可行的方案，答案就是 "YES"！否则就是 "NO"。

如何高效处理查询？

现在我们有了判断条件，但每次查询都重新计算一遍那个和式 (O(n)) 会超时的说。

注意到 g = gcd(k, m) 的取值是有限的，它只能是 m 的约数。m 最大是 5 * 10^5，它的约数个数并不会太多（最多也就两百多个）。

这启发了我们：可以预处理！

1. 预计算: 找出 m 的所有约数 d。对于每个约数 d，我们都计算出对应的和 S(d) = \sum_{i=1}^{n} ((a_i - a_{i-1}) \pmod d)。我们可以用一个哈希表（比如 C++ 的 unordered_map）来存储这些结果，mp[d] = S(d)。
2. 查询 2 k: 计算 g = gcd(k, m)，然后直接查表 mp[g]。如果 mp[g] < m，就是 "YES"，否则 "NO"。
3. 修改 1 i x: 当 a_i 的值从 old_val 变为 x 时，和式中只有两项会受影响：
   • 第 i 项： (a_i - a_{i-1}) \pmod d
   • 第 i+1 项：(a_{i+1} - a_i) \pmod d (如果 i < n) 所以，对于每一个约数 d，我们只需要 O(1) 的时间来更新 mp[d] 的值：减去旧的贡献，加上新的贡献。总的更新时间就是 O(D(m))，其中 D(m) 是 m 的约数个数。

因为 sum(n) 和 sum(q) 有总和限制，这个方法在总时间上是完全可以接受的！

看我把它变成代码魔法！ (代码实现)

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <climits>
using namespace std;

// 一个好用的取模函数，保证结果是非负的喵~
long long getM(long long x, long long mod) {
    if (mod == 0) 
        return 0;
    x %= mod;
    if (x < 0) 
        x += mod;
    return x;
}

// 迭代法求最大公约数，很快的！
long long gcd_iter(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        long long n, m, q;
        cin >> n >> m >> q;
        vector<long long> a(n+1);
        a[0] = 0; // 就像我们思路里分析的，设置 a[0] = 0
        for (int i=1; i<=n; i++) {
            cin >> a[i];
        }

        // 预处理 m 的所有约数
        vector<long long> divisors;
        long long sq = sqrt(m);
        for (long long i=1; i<=sq; i++) {
            if (m % i == 0) {
                divisors.push_back(i);
                if (i != m/i) {
                    divisors.push_back(m/i);
                }
            }
        }

        // 用哈希表存储 S(d) 的值，d 是 m 的约数
        unordered_map<long long, long long> mp;
        for (long long d : divisors) {
            mp[d] = 0;
        }

        // 初始化计算所有 S(d)
        for (long long d : divisors) {
            long long total = 0;
            for (int i=1; i<=n; i++) {
                long long diff = a[i] - a[i-1];
                total += getM(diff, d);
            }
            mp[d] = total;
        }

        while (q--) {
            int type;
            cin >> type;
            if (type == 1) { // 单点修改
                long long i, x;
                cin >> i >> x;
                long long old_val = a[i];
                
                // 对于每个约数 d，减去旧值的贡献
                for (long long d : divisors) {
                    long long diff_prev = old_val - a[i-1];
                    mp[d] -= getM(diff_prev, d);
                    // 如果不是最后一个元素，还要考虑对下一项的影响
                    if (i < n) {
                        long long diff_next = a[i+1] - old_val;
                        mp[d] -= getM(diff_next, d);
                    }
                }
                
                a[i] = x; // 更新数组
                
                // 对于每个约数 d，加上新值的贡献
                for (long long d : divisors) {
                    long long diff_prev = a[i] - a[i-1];
                    mp[d] += getM(diff_prev, d);
                    if (i < n) {
                        long long diff_next = a[i+1] - a[i];
                        mp[d] += getM(diff_next, d);
                    }
                }
            } else { // 可行性查询
                long long k;
                cin >> k;
                long long g = gcd_iter(k, m); // 关键 g = gcd(k, m)
                // 查表，判断 S(g) < m
                if (mp.find(g) != mp.end() && mp[g] < m) {
                    cout << "YES\n";
                } else {
                    cout << "NO\n";
                }
            }
        }
    }
    return 0;
}

跑得快不快呀？ (复杂度分析)

• 时间复杂度: O(sum(sqrt(m) + n * D(m) + q * (D(m) + log m))) 的说。

  • sqrt(m) 是找 m 的所有约数的时间。
  • n * D(m) 是初始化计算所有 S(d) 的时间，D(m) 是 m 的约数个数。
  • q * D(m) 是所有修改操作的总时间。
  • q * log m 是所有查询操作中计算 gcd 的总时间。
  • 因为题目保证了所有测试用例的 n 的总和以及 q 的总和都不超过 10^5，所以 sum(n * D(m)) 的总和是在可接受范围内的，不会超时哦！

• 空间复杂度: O(n + D(m)) 的说。

  • O(n) 用来存储数组 a。
  • O(D(m)) 用来存储 m 的约数和我们那个万能的哈希表 mp。

这次又学到了什么呢？ (知识点与总结)

这道题真是一次愉快的冒险呢！我们来总结一下这次的收获吧~

1. 问题转化: 最关键的一步！把复杂的 "模 m 加 k" 操作，通过数论知识转化为了更简洁的 "模 gcd(k,m) 同余" 问题。这是解开谜题的钥匙喵！
2. 贪心构造: 面对 "是否存在" 这类问题，贪心是一个非常有力的武器。我们通过构造一个最极端（在这里是值最小）的合法情况，来判断是否存在任何可行解。
3. 预计算与缓存: 当问题的参数（这里的 g=gcd(k,m)）取值范围有限时，可以考虑预计算所有可能情况的结果并缓存起来。这样查询时就能做到飞快！
4. 高效更新: 我们的缓存（哈希表 mp）能够在 O(D(m)) 的时间内响应单点修改，这得益于修改操作只影响了局部（两个差值）的性质。
5. 小技巧: 引入 a_0=0 让我们的求和公式 \sum ((a_i - a_{i-1}) \pmod g) 变得非常整洁，避免了对 a_1 的特殊处理。

干得漂亮，又解决了一道难题喵！继续加油，向着更厉害的算法大师前进呐！