Moe's CF Life

Appearance

D. The Child and Sequence - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 250 (Div. 1) 标签: data structures, math 难度: *2300

题目大意喵~ ​

主人你好呀~！这道题是关于维护一个序列的呐。我们需要处理一个有 n 个整数的序列，并执行 m 次操作，操作有三种类型哦：

  1. 区间求和: 给定 l 和 r，计算出从 a[l] 到 a[r] 所有数字的总和。
  2. 区间取模: 给定 l、r 和 x，将区间 [l, r] 内的每个数 a[i] 都更新为 a[i] % x。
  3. 单点修改: 给定 k 和 x，将 a[k] 的值修改为 x。

对于每一个求和操作，我们都需要输出对应的答案。要加油哦，喵~！

解题思路分析喵！ ​

喵呜~ 这道题有区间查询、单点修改，还有一个看起来很棘手的区间取模操作！看到区间操作，我们的小脑袋瓜里是不是立刻就想到了线段树或者树状数组呀？

  • 操作1（区间求和） 和 操作3（单点修改） 都是线段树的经典操作，非常简单就能实现，没什么好担心的说。

  • 真正的挑战在于 操作2（区间取模）。这个操作可不能用普通的懒标记（lazy propagation）来解决哦！为什么呢？因为取模操作对区间里每个数的影响是不同的，它依赖于每个数自身的值。比如，一个区间 [5, 10] 对 4 取模，5 变成 1，而 10 变成 2。减少的值不一样，我们没法用一个统一的懒标记来表示这个变化。

那该怎么办呢？难道要对区间里的每个数都进行一次单点修改吗？那样一次操作就是 O(n log n)，肯定会超时的说！

别急别急，让我们来仔细观察一下取模操作的性质喵~ a[i] = a[i] % x 当 a[i] < x 时，a[i] % x 的结果还是 a[i]，数值根本不会变！ 当 a[i] >= x 时，a[i] 会变成一个严格小于 x 的数，也就是说，a[i] 的值会变小。

这个性质太关键啦！如果一个区间内的所有数都已经小于取模的 x，那这次取模操作对这个区间就完全没有影响了！我们就可以直接跳过对这个区间的修改，对不对？

于是，一个绝妙的想法就诞生了：我们可以改造一下我们的线段树！除了维护区间的和 sum 之外，我们再多维护一个 区间的最大值 max。

当我们要对区间 [l, r] 进行取模 x 的操作时，我们在线段树上递归。对于当前节点所代表的区间：

  1. 如果这个区间的最大值 max 都小于 x，那就说明这个区间里的所有数都小于 x。取模操作不会改变任何一个数字！所以我们就可以心安理得地剪枝，直接 return，不再往下递归了。这大大减少了我们的计算量！
  2. 如果这个区间的最大值 max 大于等于 x，说明区间里至少有一个数需要被修改。我们就没办法偷懒了，只能继续往下递归，直到找到那些需要修改的叶子节点，然后对它们进行单点修改，再把结果一层层更新回来。

因为每次有效的取模操作都会让数字变小（至少减半，想一想为什么~ 当 a >= x 时，a % x < x），所以每个数字被成功修改的次数是有限的（大概是 log(a[i]) 级别）。因此，即使我们看起来是在“暴力”递归修改，但加上了这个聪明的剪枝后，总的复杂度是完全可以接受的！

总结一下我们的策略：

  • 使用线段树，每个节点维护 sum (区间和) 和 max (区间最大值)。
  • 区间求和 和 单点修改 都是标准线段树操作。
  • 区间取模 时，递归修改。但如果当前区间的最大值已经小于模数 x，就进行剪枝，直接返回。

这样一来，问题就迎刃而解啦，喵~！

代码实现时间到！ ​

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

using namespace std;

const int MAXN = 100005;

// 线段树的数组，4*N的空间是标配哦
long long tree_sum[4 * MAXN]; // 维护区间和
int tree_max[4 * MAXN];      // 维护区间最大值
int a[MAXN];                 // 原始数组
int n, m;

// pull操作，用左右子节点的信息更新父节点
void pull(int p) {
    tree_sum[p] = tree_sum[2 * p] + tree_sum[2 * p + 1];
    tree_max[p] = max(tree_max[2 * p], tree_max[2 * p + 1]);
}

// build操作，递归建树
void build(int p, int L, int R) {
    if (L == R) {
        // 到达叶子节点，直接用初始值填充
        tree_sum[p] = a[L];
        tree_max[p] = a[L];
        return;
    }
    int mid = L + (R - L) / 2;
    build(2 * p, L, mid);
    build(2 * p + 1, mid + 1, R);
    pull(p); // 别忘了从下往上更新信息
}

// 区间求和查询
long long query_sum(int p, int L, int R, int qL, int qR) {
    // 查询区间和当前节点区间没有交集
    if (qL > R || qR < L) {
        return 0;
    }
    // 查询区间完全覆盖当前节点区间
    if (qL <= L && R <= qR) {
        return tree_sum[p];
    }
    int mid = L + (R - L) / 2;
    // 递归查询左右子树
    return query_sum(2 * p, L, mid, qL, qR) + query_sum(2 * p + 1, mid + 1, R, qL, qR);
}

// 单点修改
void update_set(int p, int L, int R, int k, int x) {
    if (L == R) {
        // 找到要修改的叶子节点
        tree_sum[p] = x;
        tree_max[p] = x;
        return;
    }
    int mid = L + (R - L) / 2;
    if (k <= mid) {
        update_set(2 * p, L, mid, k, x);
    } else {
        update_set(2 * p + 1, mid + 1, R, k, x);
    }
    pull(p); // 记得更新父节点
}

// 区间取模，这是最核心的部分喵！
void update_mod(int p, int L, int R, int qL, int qR, int x) {
    // [剪枝核心] 如果当前区间的最大值都比x小，取模操作无意义，直接返回
    if (tree_max[p] < x) {
        return;
    }
    // 如果当前区间和查询区间没有交集，也返回
    if (qL > R || qR < L) {
        return;
    }
    // 到达叶子节点，进行实际的取模操作
    if (L == R) {
        tree_sum[p] %= x;
        tree_max[p] %= x;
        return;
    }
    
    int mid = L + (R - L) / 2;
    // 递归处理左右子区间
    update_mod(2 * p, L, mid, qL, qR, x);
    update_mod(2 * p + 1, mid + 1, R, qL, qR, x);
    pull(p); // 操作完成后，更新父节点信息
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    build(1, 1, n);

    for (int i = 0; i < m; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            cout << query_sum(1, 1, n, l, r) << "\n";
        } else if (type == 2) {
            int l, r, x;
            cin >> l >> r >> x;
            update_mod(1, 1, n, l, r, x);
        } else {
            int k, x;
            cin >> k >> x;
            update_set(1, 1, n, k, x);
        }
    }

    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O((m + n log A) * log n) 的说。
    • m 是操作次数，对于查询和单点修改，每次都是 O(log n)。
    • 对于区间取模操作，由于我们有剪枝，所以不是每次都 O(n)。一个数 v 被 x 取模后，如果值发生变化，新的值会严格小于 v。一个数最多被有效修改 O(log A) 次（A 是数的最大值）。所以所有数被修改的总次数是 O(n log A)。每次修改一个叶子节点需要 O(log n) 的时间。所以总的时间复杂度是比较玄学的 O((m + n log A) * log n)，但它足够快啦！
  • 空间复杂度: O(n) 的说。
    • 我们主要的空间开销是线段树数组，大小是 4 * n，所以是 O(n) 级别的。

知识点与总结 ​

这道题真是一道非常棒的线段树练习题呢，喵~ 它教会了我们一个重要的技巧：

  1. 线段树的灵活应用: 不要把线段树想得太死板！除了维护 sum，我们还可以根据题目需要维护 max, min, gcd 等等各种信息。
  2. 利用操作性质进行剪枝: 当遇到无法使用懒标记的复杂区间操作时，可以深入分析操作本身的性质。像本题的取模操作，它具有让数值单调递减（或不变）的特性，这就为我们提供了剪枝的可能。
  3. 势能分析思想: 这种剪枝优化的复杂度分析方法，有时也被称为“势能分析”。可以理解为，每次有效的修改都会消耗掉整个系统的“势能”（比如所有数的总和或者某个别的指标），而“势能”的总量是有限的，所以总的修改次数也是有限的。类似的技巧还可以用于区间开方、区间取 phi 等操作上。

是不是很有趣呀？喵~ 只要发现了取模操作的性质，问题就迎刃而解啦！希望这篇题解能帮助到你，继续加油哦！

Released under the MIT License.

Copyright © 2024-present Moe