维护序列 - 题解

标签与难度

标签: 矩阵快速幂, 差分数组, 线性代数, 斐波那契, 数据结构, 模运算 难度: 2000

题目大意喵~

主人你好呀，喵~ 这道题是这样的：

我们有两个长度都是 $n$ 的序列 $a$ 和 $b$。然后会有 $m$ 次操作。每一次操作会给我们三个数字 $l, r, k$。

这个操作的意思是，对于从 $l$ 到 $r$ 的每一个位置 $i$，我们都要对 $(a_i, b_i)$ 这对数字执行 $k$ 次一个奇妙的变换。这个变换是：

1. 先交换 $a_i$ 和 $b_i$ 的值。
2. 然后，新的 $a_i$ 会变成（新的 $a_i$）+（新的 $b_i$）。

等所有 $m$ 次操作都下达完毕后，我们需要一次性计算出并输出最终的序列 $a$ 和 $b$。所有计算结果都要对 $1000000007$ 取模哦！

解题思路分析

这道题看起来操作好多，范围也很大，直接模拟肯定会超时的说！但是不要怕，让我来带你一步步拆解它，喵~

第一步：化繁为简，处理区间操作

首先，题目中所有的操作都是对一个区间 [l, r] 进行的。而且，我们只需要在所有操作都结束后才输出结果。这是一个很重要的信号哦！这意味着我们可以先“记账”，最后再统一结算。

对于每个位置 $i$，它可能被很多个不同的 [l, r] 区间覆盖。我们其实只关心在所有操作结束后，位置 $i$ 上的这个奇妙变换总共被执行了多少次。

这不就是经典的差分数组的应用场景嘛！我们可以创建一个差分数组 op_counts，对于每个操作 l, r, k，我们就在 op_counts[l] 上加上 $k$，在 op_counts[r+1] 上减去 $k$。

当所有 $m$ 个操作都处理完后，我们对 op_counts 数组求一个前缀和。这样 op_counts[i] 就代表了第 $i$ 个位置总共需要执行的变换次数，我们记为 $K_i$。这个过程的时间复杂度只有 $O(n+m)$，非常快！

现在问题就简化为：对于每个位置 $i$（从 $1$ 到 $n$），给定初始值 $(a_i, b_i)$，求经过 $K_i$ 次变换后的结果。不同位置之间的计算是完全独立的，真好呐！

第二步：分析单次变换的本质

接下来，我们来仔细研究一下这个奇妙的变换。 假设在某个位置，当前的值是 $(a_{old}, b_{old})$。

1. swap(a, b): 值变成了 $(b_{old}, a_{old})$。
2. a = a + b: 这里的 a 和 b 是交换后的值。所以新的 $a$ 变成了 $b_{old} + a_{old}$。而 $b$ 的值没变，还是 $a_{old}$。

所以，一次变换把 $(a_{old}, b_{old})$ 变成了 $(a_{old} + b_{old}, a_{old})$。 我们把新值记为 $(a_{new}, b_{new})$，那么：

$$\begin{cases} a_{new} = 1 \cdot a_{old} + 1 \cdot b_{old} \\ b_{new} = 1 \cdot a_{old} + 0 \cdot b_{old} \end{cases}$$

呜喵！主人你看，这是一个线性的变换！凡是线性的变换，我们都可以用一个神奇的工具——矩阵来表示！

$$\begin{pmatrix} a_{new} \\ b_{new} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_{old} \\ b_{old} \end{pmatrix}$$

我们把这个 $2 \times 2$ 的矩阵叫做转移矩阵 $T$。

第三步：矩阵快速幂登场！

对一个位置 $i$ 进行 $K_i$ 次变换，就相当于用它的初始值向量 $\begin{pmatrix} a_i \\ b_i \end{pmatrix}$ 连续左乘 $K_i$ 次转移矩阵 $T$。也就是：

$$\begin{pmatrix} a_{final} \\ b_{final} \end{pmatrix} = T \cdot T \cdot \dots \cdot T \cdot \begin{pmatrix} a_{initial} \\ b_{initial} \end{pmatrix} = T^{K_i} \begin{pmatrix} a_{initial} \\ b_{initial} \end{pmatrix}$$

$K_i$ 的值可能会非常大（最大可达 $10^5 \times 10^5 = 10^{10}$），我们当然不能真的乘那么多次。但是，求一个数的幂次可以用快速幂，求一个矩阵的幂次自然也可以用矩阵快速幂呀！

矩阵快速幂的原理和普通快速幂一模一样，只是把数字的乘法换成了矩阵的乘法。计算 $T^k$ 的时间复杂度是 $O(d^3 \log k)$，其中 $d$ 是矩阵的维度。在这里 $d=2$ 是个常数，所以复杂度是 $O(\log k)$，超级快！

第四步：最终的算法流程

好啦，思路已经清晰了，我们来总结一下完整的算法步骤：

1. 读入 $n, m$ 和初始的 $a, b$ 序列。
2. 创建一个差分数组 k_counts（大小为 $n+2$ 就够了）。
3. 遍历 $m$ 个操作，对于每个 l, r, k，执行 k_counts[l] += k 和 k_counts[r+1] -= k。
4. 计算 k_counts 的前缀和，得到每个位置 $i$ 的总操作次数 $K_i$。
5. 定义我们的转移矩阵 $T = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$。
6. 遍历每个位置 $i$ 从 $1$ 到 $n$： a. 获取总操作次数 $K_i = \text{k\_counts}[i]$。 b. 如果 $K_i=0$，那么 $a_i, b_i$ 不变。 c. 如果 $K_i>0$，使用矩阵快速幂计算出 $M = T^{K_i}$。 d. 用矩阵 $M$ 更新 $(a_i, b_i)$： $$ \begin{pmatrix} a_i' \ b_i' \end{pmatrix} = M \begin{pmatrix} a_i \ b_i \end{pmatrix} $$
7. 输出最终的 $a, b$ 序列。

小优化: 可能会有很多位置的 $K_i$ 值是相同的。我们可以用一个 map 来缓存已经计算过的 $T^{K_i}$ 的结果，避免重复计算，让程序跑得更快一点，喵~

代码实现

下面是我根据上面的思路，精心为你准备的代码哦！注释写得很详细，希望能帮到你，喵~

#include <iostream>
#include <vector>
#include <map>

using namespace std;

// 定义模数
const long long MOD = 1000000007;

// 定义一个 2x2 矩阵结构体，喵~
struct Matrix {
    long long mat[2][2];

    // 默认构造一个零矩阵
    Matrix() {
        mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0;
    }
};

// 矩阵乘法，要小心计算顺序和取模哦
Matrix multiply(const Matrix& A, const Matrix& B) {
    Matrix C;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
            }
        }
    }
    return C;
}

// 矩阵快速幂，和普通快速幂一样的思路！
Matrix matrix_power(Matrix base, long long exp) {
    Matrix result;
    // 初始化为单位矩阵
    result.mat[0][0] = result.mat[1][1] = 1;

    while (exp > 0) {
        if (exp % 2 == 1) {
            result = multiply(result, base);
        }
        base = multiply(base, base);
        exp /= 2;
    }
    return result;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    // 差分数组，用来统计每个位置的总操作次数
    // 大小为 n+1 就够了，因为 r+1 最多是 n+1
    vector<long long> k_counts(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int l, r;
        long long k;
        cin >> l >> r >> k;
        // 差分操作：l处增加k，r+1处减去k
        // 题目下标是1-based，我们代码是0-based，所以要-1
        k_counts[l - 1] += k;
        if (r < n) {
            k_counts[r] -= k;
        }
    }

    // 计算前缀和，得到每个位置 i 的真实操作次数 K_i
    for (int i = 1; i < n; ++i) {
        k_counts[i] += k_counts[i - 1];
    }
    
    // 用 map 来缓存计算过的矩阵幂，避免重复劳动
    map<long long, Matrix> memo;

    // 基础转移矩阵 T
    Matrix T;
    T.mat[0][0] = 1; T.mat[0][1] = 1;
    T.mat[1][0] = 1; T.mat[1][1] = 0;

    // 对每个位置进行最终计算
    vector<long long> final_a(n), final_b(n);
    for (int i = 0; i < n; ++i) {
        long long k = k_counts[i];
        
        if (k == 0) {
            // 如果操作次数为0，值不变
            final_a[i] = a[i];
            final_b[i] = b[i];
            continue;
        }

        Matrix transform_matrix;
        // 检查缓存里有没有
        if (memo.find(k) != memo.end()) {
            transform_matrix = memo[k];
        } else {
            // 没有就计算一次，并存入缓存
            transform_matrix = matrix_power(T, k);
            memo[k] = transform_matrix;
        }

        // 应用变换矩阵
        long long initial_a = a[i];
        long long initial_b = b[i];

        final_a[i] = (transform_matrix.mat[0][0] * initial_a + transform_matrix.mat[0][1] * initial_b) % MOD;
        final_b[i] = (transform_matrix.mat[1][0] * initial_a + transform_matrix.mat[1][1] * initial_b) % MOD;
    }

    // 输出结果，喵~
    for (int i = 0; i < n; ++i) {
        cout << final_a[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;
    for (int i = 0; i < n; ++i) {
        cout << final_b[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

复杂度分析

• 时间复杂度: $O(m + n + U \cdot \log K_{max})$
  • 读入数据是 $O(n+m)$。
  • 处理差分数组是 $O(m)$，计算前缀和是 $O(n)$。
  • 主要耗时在于计算矩阵幂。设共有 $U$ 个不同的操作次数 $K_i$，其中最大值为 $K_{max}$。我们对每个独特的 $K_i$ 值进行一次矩阵快速幂，复杂度为 $O(\log K_i)$。总共是 $O(U \cdot \log K_{max})$。在最坏情况下，$U$ 可能是 $n$，所以总时间复杂度可以看作是 $O(m + n \log K_{max})$。
• 空间复杂度: $O(n)$
  • 我们用了几个大小为 $n$ 的 vector 来存储序列 $a, b$ 和差分数组 k_counts。
  • map 最多会存储 $n$ 个不同的矩阵，所以空间是 $O(n)$。
  • 总的空间复杂度是 $O(n)$。

知识点总结

这道题真是一次有趣的冒险呢！我们用到了好几个强大的工具：

1. 差分数组: 它是处理多个区间修改、单点查询（或者说，最终状态查询）的利器！通过在区间的端点做标记，用 $O(m)$ 的时间记录下所有操作，再用 $O(n)$ 的时间一次性算出每个点的最终状态，非常高效。
2. 线性变换与矩阵: 能够发现一个操作的本质是线性变换，并将其模型化为矩阵，是解决这类问题的关键一步。这需要一点点线代知识和敏锐的观察力，喵~
3. 矩阵快速幂: 它是解决线性递推问题的终极武器之一！一旦能把问题转化为求一个矩阵的高次幂，就可以用它来大大加速计算过程。
4. 记忆化/缓存: 当发现需要多次计算相同子问题（比如求同一个 $k$ 值的矩阵幂）时，使用 map 或哈希表进行缓存是一个非常有效的优化技巧。

希望这篇题解能对主人有所帮助！要继续加油哦，喵~