白树台学园 (hard version) - 题解

标签与难度

标签: 数据结构, 线段树, 矩阵, 动态规划, 期望, 强制在线难度: 2600

题目大意喵~

这道题是说，我们有一个序列，序列里的每个元素都有一个颜色。但是这个颜色不是固定的哦，而是从一个给定的区间 [L, R] 里随机选的，每个颜色被选中的概率都一样。

我们会有两种操作，喵~

修改操作: 在序列的末尾增加一个新的元素，并告诉你它的颜色随机区间 [L, R]。
查询操作: 给你一个颜色区间 [l, r]，问如果我们只关心这个区间的颜色，从序列中等概率随机选取一个子区间 [i, j]（1 <= i <= j <= n），这个子区间中不同颜色的期望数量是多少？

所有的操作都是强制在线的，也就是说，每次操作的输入都依赖于上一次查询的答案。所以我们必须算完一个才能知道下一个是什么，不能离线处理呢，喵。

解题思路分析

这道题看起来好复杂呀，又是期望，又是随机，还有区间查询和单点修改（在末尾增加元素），真是对我智慧的巨大考验呢，喵~ 不过别怕，我们一步一步来拆解它！

期望的魔法拆解！

首先，我们要解决的是期望问题。期望问题有一个超级好用的性质，叫做期望的线性性。简单来说，就是“总的期望”等于“各个部分期望的和”。

对于一个查询 [l, r]，我们要求的期望颜色数，可以分解成：

E(\text{总颜色数}) = \sum_{c=l}^{r} E(\text{颜色 } c \text{ 是否出现})

而颜色 $c$ 是否出现的期望，就等于它出现的概率 $P(\text{颜色 } c \text{ 出现})$ 。所以，问题就变成了计算每种颜色 $c \in [l, r]$ 在随机子区间中出现的概率，然后把它们加起来！

E(\text{总颜色数}) = \sum_{c=l}^{r} P(\text{颜色 } c \text{ 出现})

概率的正反思考

直接计算一个颜色出现的概率有点麻烦，我们不妨反过来想：计算它不出现的概率。

P(\text{出现}) = 1 - P(\text{不出现})

所以，我们的目标变成了：

E = \sum_{c=l}^{r} (1 - P(\text{颜色 } c \text{ 不出现})) = (r - l + 1) - \sum_{c=l}^{r} P(\text{颜色 } c \text{ 不出现})

一个颜色 $c$ 在一个随机子区间中不出现，意思是，我们先随机选一个子区间 [i, j]，然后发现 [i, j] 中所有位置的颜色都不是 $c$ 。设当前序列长度为 $N$ ，总共有 $N(N+1)/2$ 个子区间。

P(\text{颜色 } c \text{ 不出现}) = \frac{\text{不含颜色 } c \text{ 的子区间数量}}{\text{总子区间数量}}

总子区间数量是 $N_{total} = \frac{N(N+1)}{2}$ 。我们只需要求出对于每个颜色 $c$ ，不含它的子区间数量，然后加起来。这还是有点麻烦，因为每个位置的颜色是随机的。

让我们再换个角度，利用全期望公式。

P(\text{颜色 } c \text{ 不出现}) = \sum_{1 \le i \le j \le N} P(\text{选到子区间 } [i, j]) \times P(\text{区间 } [i, j] \text{ 不含 } c)

因为每个子区间是等概率选的，所以 $P(\text{选到子区间 } [i, j]) = \frac{1}{N_{total}}$ 。 $P(\text{区间 } [i, j] \text{ 不含 } c)$ 是指，对于所有 $k \in [i, j]$ ，第 $k$ 个元素的颜色都不是 $c$ 。由于每个位置的颜色是独立随机的，这个概率就是：

P(\text{区间 } [i, j] \text{ 不含 } c) = \prod_{k=i}^{j} P(\text{第 } k \text{ 个元素的颜色} \neq c)

设第 $k$ 个元素的颜色区间是 $[L_k, R_k]$ ，长度为 $W_k = R_k - L_k + 1$ 。如果 $c \in [L_k, R_k]$ ，那么第 $k$ 个元素颜色为 $c$ 的概率是 $1/W_k$ ，颜色不为 $c$ 的概率就是 $1 - 1/W_k$ 。如果 $c \notin [L_k, R_k]$ ，那颜色不为 $c$ 的概率就是 $1$ 。

把这些都代入我们最初的期望公式，我们要求的就是：

E = (r - l + 1) - \frac{1}{N_{total}} \sum_{c=l}^{r} \sum_{1 \le i \le j \le N} \prod_{k=i}^{j} P(\text{第 } k \text{ 个元素的颜色} \neq c)

这个式子看起来太吓人了！但别灰心，我们的目标其实是计算 $\sum_{c=l}^{r} \left( \sum_{1 \le i \le j \le N} \prod_{k=i}^{j} P_k(c) \right)$ ，这里 $P_k(c)$ 是第 $k$ 个位置颜色不为 $c$ 的概率。

DP 与矩阵的华丽变身！

我们发现，对于一个固定的颜色 $c$ ，计算 $\sum_{1 \le i \le j \le N} \prod_{k=i}^{j} P_k(c)$ 是一个经典的 DP 问题。设 $S_j(c) = \sum_{i=1}^{j} \prod_{k=i}^{j} P_k(c)$ ，表示以 $j$ 结尾的所有子区间的“不含 $c$ 概率”之和。我们可以得到递推关系：

S_j(c) = P_j(c) \cdot \left( \sum_{i=1}^{j-1} \prod_{k=i}^{j-1} P_k(c) + 1 \right) = P_j(c) \cdot (S_{j-1}(c) + 1)

我们最终要求的是 $\sum_{j=1}^{N} S_j(c)$ 。设 $T_j(c) = \sum_{k=1}^{j} S_k(c)$ 。那么 $T_j(c) = T_{j-1}(c) + S_j(c) = T_{j-1}(c) + P_j(c) \cdot (S_{j-1}(c) + 1)$ 。

这个 DP 状态转移是线性的！我们可以用矩阵来表示它。定义状态向量为 $\begin{pmatrix} S_j(c) \\ T_j(c) \\ 1 \end{pmatrix}$ 。从 $j-1$ 到 $j$ 的转移可以写成：

\begin{pmatrix} S_j(c) \\ T_j(c) \\ 1 \end{pmatrix} = \begin{pmatrix} P_j(c) & 0 & P_j(c) \\ P_j(c) & 1 & P_j(c) \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} S_{j-1}(c) \\ T_{j-1}(c) \\ 1 \end{pmatrix}

初始状态是 $S_0(c)=0, T_0(c)=0$ ，即 $\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}$ 。处理完 $N$ 个元素后，最终的 $T_N(c)$ 就是我们想要的。

线段树的舞台！

每次修改是在序列末尾加一个元素，相当于在我们的 DP 过程中增加一步。每次查询是问一个颜色区间 [l, r] 的答案。 $P_j(c)$ 的值只取决于 $c$ 是否在第 $j$ 个元素的颜色区间 $[L_j, R_j]$ 内。这启发我们用数据结构来维护所有颜色的 DP 状态！我们可以建一棵关于颜色 1 到 M 的线段树（M是颜色最大值）。

线段树的每个节点 p 代表一个颜色区间，我们在这个节点里维护：

sum_S: 区间内所有颜色的 $S(c)$ 之和。
sum_T: 区间内所有颜色的 $T(c)$ 之和。
len: 区间长度。
lazy_matrix: 一个 $3 \times 3$ 的懒标记矩阵，表示待应用到这个区间的变换。

当我们在序列末尾加入第 $k$ 个元素，其颜色范围为 $[L_k, R_k]$ 时：

对于颜色 $c \notin [L_k, R_k]$ ，其 $P_k(c) = 1$ 。对应的转移矩阵是 $M_{out} = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}$ 。
对于颜色 $c \in [L_k, R_k]$ ，其 $P_k(c) = 1 - \frac{1}{R_k-L_k+1} = q_k$ 。对应的转移矩阵是 $M_{in} = \begin{pmatrix} q_k & 0 & q_k \\ q_k & 1 & q_k \\ 0 & 0 & 1 \end{pmatrix}$ 。

一次添加操作，相当于给所有颜色的状态向量左乘上对应的转移矩阵。这可以用线段树的区间更新来高效完成！我们可以把这个操作分解成两步：

首先，给所有颜色 [1, M] 都应用 $M_{out}$ 变换。
然后，对于颜色区间 [L_k, R_k]，它们的变换应该是 $M_{in}$ 而不是 $M_{out}$ 。所以我们需要再给它们乘上一个“修正矩阵” $M_{corr}$ ，使得 $M_{corr} \cdot M_{out} = M_{in}$ 。可以解出 $M_{corr} = M_{in} \cdot (M_{out})^{-1} = \begin{pmatrix} q_k & 0 & 0 \\ q_k-1 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ 。

所以，每次添加元素的操作就变成了：

对线段树的 [1, M] 区间进行一次矩阵更新（左乘 $M_{out}$ ）。
对线段树的 [L_k, R_k] 区间进行一次矩阵更新（左乘 $M_{corr}$ ）。

查询操作: 对于查询 [l, r]，我们在线段树上查询这个颜色区间的 sum_T。设结果为 total_T。那么 $\sum_{c=l}^{r} T_N(c) = \text{total\_T}$ 。代入期望公式，最终答案就是：

E = (r - l + 1) - \text{total\_T} \cdot \left(\frac{N(N+1)}{2}\right)^{-1} \pmod{M}

其中 $N$ 是当前序列的长度。

这样，我们就把一个复杂的期望问题转化成了线段树维护矩阵的模板题啦！是不是很奇妙，喵~

代码实现

这是我根据上面的思路，精心重构的全新代码哦！希望能帮助你理解，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

// 使用 long long 防止溢出喵
using ll = long long;

const int MOD = 998244353;
const int MAX_COLORS = 100005; // 题目给定的颜色最大范围

// 快速幂，用来求逆元
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 求 x 在模 MOD 下的逆元
ll modInverse(ll n) {
    return power(n, MOD - 2);
}

// 3x3 矩阵结构体
struct Matrix {
    ll mat[3][3];

    Matrix() {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                mat[i][j] = 0;
            }
        }
    }

    // 单位矩阵
    static Matrix identity() {
        Matrix I;
        for (int i = 0; i < 3; ++i) {
            I.mat[i][i] = 1;
        }
        return I;
    }

    // 矩阵乘法
    Matrix operator*(const Matrix& other) const {
        Matrix result;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                for (int k = 0; k < 3; ++k) {
                    result.mat[i][j] = (result.mat[i][j] + mat[i][k] * other.mat[k][j]) % MOD;
                }
            }
        }
        return result;
    }
};

// 线段树节点
struct Node {
    ll sum_S, sum_T;
    Matrix lazy;

    Node() : sum_S(0), sum_T(0), lazy(Matrix::identity()) {}
};

vector<Node> tree;
int color_range_size;

// 将懒人标记应用到当前节点
void apply_lazy(int p, int len) {
    Node& node = tree[p];
    ll new_sum_S = (node.lazy.mat[0][0] * node.sum_S + node.lazy.mat[0][1] * node.sum_T + node.lazy.mat[0][2] * len) % MOD;
    ll new_sum_T = (node.lazy.mat[1][0] * node.sum_S + node.lazy.mat[1][1] * node.sum_T + node.lazy.mat[1][2] * len) % MOD;
    node.sum_S = new_sum_S;
    node.sum_T = new_sum_T;
}

// 把懒人标记向下传递
void push_down(int p) {
    if (tree[p].lazy.mat[0][0] != 1 || tree[p].lazy.mat[0][1] != 0 || tree[p].lazy.mat[0][2] != 0 ||
        tree[p].lazy.mat[1][0] != 1 || tree[p].lazy.mat[1][1] != 1 || tree[p].lazy.mat[1][2] != 0) { // 检查是否是单位矩阵的简写
        
        tree[2 * p].lazy = tree[p].lazy * tree[2 * p].lazy;
        tree[2 * p + 1].lazy = tree[p].lazy * tree[2 * p + 1].lazy;
        
        tree[p].lazy = Matrix::identity();
    }
}

// 合并左右子节点的信息
void push_up(int p, int l, int r) {
    int mid = l + (r - l) / 2;
    apply_lazy(2 * p, mid - l + 1);
    apply_lazy(2 * p + 1, r - mid);
    tree[p].sum_S = (tree[2 * p].sum_S + tree[2 * p + 1].sum_S) % MOD;
    tree[p].sum_T = (tree[2 * p].sum_T + tree[2 * p + 1].sum_T) % MOD;
}

// 区间更新
void update(int p, int l, int r, int ql, int qr, const Matrix& transform) {
    apply_lazy(p, r - l + 1);
    if (l > qr || r < ql) return;
    if (ql <= l && r <= qr) {
        tree[p].lazy = transform * tree[p].lazy;
        apply_lazy(p, r - l + 1);
        return;
    }

    push_down(p);

    int mid = l + (r - l) / 2;
    update(2 * p, l, mid, ql, qr, transform);
    update(2 * p + 1, mid + 1, r, ql, qr, transform);

    push_up(p, l, r);
}

// 区间查询
ll query(int p, int l, int r, int ql, int qr) {
    apply_lazy(p, r - l + 1);
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) {
        return tree[p].sum_T;
    }

    push_down(p);
    
    int mid = l + (r - l) / 2;
    ll res = (query(2 * p, l, mid, ql, qr) + query(2 * p + 1, mid + 1, r, ql, qr)) % MOD;

    push_up(p, l, r);
    return res;
}

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

    int n_init, q;
    cin >> n_init >> color_range_size >> q;

    tree.resize(4 * color_range_size + 4);
    
    ll current_n = 0;
    ll last_ans = 0;
    
    // 处理初始的 n_init 个元素
    for (int i = 0; i < n_init; ++i) {
        current_n++;
        ll l, r;
        cin >> l >> r;

        ll prob_complement = (1 - modInverse(r - l + 1) + MOD) % MOD;
        
        Matrix m_out, m_corr;
        m_out.mat[0][0] = 1; m_out.mat[0][2] = 1;
        m_out.mat[1][0] = 1; m_out.mat[1][1] = 1; m_out.mat[1][2] = 1;
        m_out.mat[2][2] = 1;

        m_corr.mat[0][0] = prob_complement;
        m_corr.mat[1][0] = (prob_complement - 1 + MOD) % MOD;
        m_corr.mat[1][1] = 1;
        m_corr.mat[2][2] = 1;

        update(1, 1, color_range_size, 1, color_range_size, m_out);
        update(1, 1, color_range_size, l, r, m_corr);
    }
    
    // 处理 q 次操作
    while (q--) {
        int type;
        ll l_in, r_in;
        cin >> type >> l_in >> r_in;
        
        ll l = (l_in ^ last_ans) % color_range_size + 1;
        ll r = (r_in ^ last_ans) % color_range_size + 1;
        if (l > r) swap(l, r);

        if (type == 1) {
            current_n++;
            ll prob_complement = (1 - modInverse(r - l + 1) + MOD) % MOD;

            Matrix m_out, m_corr;
            m_out.mat[0][0] = 1; m_out.mat[0][2] = 1;
            m_out.mat[1][0] = 1; m_out.mat[1][1] = 1; m_out.mat[1][2] = 1;
            m_out.mat[2][2] = 1;

            m_corr.mat[0][0] = prob_complement;
            m_corr.mat[1][0] = (prob_complement - 1 + MOD) % MOD;
            m_corr.mat[1][1] = 1;
            m_corr.mat[2][2] = 1;

            update(1, 1, color_range_size, 1, color_range_size, m_out);
            update(1, 1, color_range_size, l, r, m_corr);
        } else {
            ll total_subsegments = current_n * (current_n + 1) / 2 % MOD;
            ll inv_total_sub = modInverse(total_subsegments);
            
            ll sum_T = query(1, 1, color_range_size, l, r);
            
            ll term_to_subtract = (sum_T * inv_total_sub) % MOD;
            ll ans = ((r - l + 1) - term_to_subtract + MOD) % MOD;
            
            cout << ans << "\n";
            last_ans = ans;
        }
    }

    return 0;
}

复杂度分析

时间复杂度: $O((N_{init} + Q) \cdot \log M)$ ，其中 $N_{init}$ 是初始元素数量， $Q$ 是操作次数， $M$ 是颜色的最大范围。每次添加元素或查询，我们都需要在线段树上进行操作，线段树的高度是 $O(\log M)$ 。矩阵乘法是 $3 \times 3$ 的，可以看作是常数时间 $O(1)$ 的操作。所以每次操作的复杂度是 $O(\log M)$ 。
空间复杂度: $O(M)$ ，主要是线段树占用的空间。线段树需要大约 $4M$ 个节点。

知识点总结

这道题是多种算法思想的完美结合，喵~

期望的线性性: 这是解决期望问题的钥匙，它能把复杂问题分解成一个个小问题的和。
动态规划 (DP): 我们通过建立 DP 状态和递推式，找到了问题的核心结构。
矩阵加速 DP: 当 DP 转移是线性的时候，就可以用矩阵来表示和加速。这是从 $O(N)$ 优化到 $O(\log N)$ 的常用技巧，在这里我们用它来表示状态的“一步”转移。
线段树: 强大的区间数据结构！这里我们用它来维护一个颜色区间内的 DP 状态之和。
线段树与懒标记: 特别是，我们用了矩阵懒标记。当一个操作要应用到一大段连续区间时，懒标记可以把多次修改合并，大大提高效率。
强制在线: 提醒我们必须按顺序处理操作，不能使用离线算法。

通过这道题，我们可以学到如何将一个看似棘手的期望问题，一步步转化为数据结构可以解决的模型。这需要敏锐的观察力和对各种算法工具的熟练运用，是一次非常棒的思维锻炼，喵！

白树台学园 (hard version) - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

期望的魔法拆解！ ​

概率的正反思考 ​

DP 与矩阵的华丽变身！ ​

线段树的舞台！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​