SorttheStringsRevision - 题解

标签与难度

标签: 笛卡尔树, 差分数组, 排序, 字符串, 哈希, 数据结构, 伪随机难度: 2300

题目大意喵~

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

我们有 $n+1$ 个长度为 $n$ 的字符串，编号从 $s_0$ 到 $s_n$ 。

初始字符串 $s_0$ 是一个很有规律的串，它的第 $i$ 个字符是 $i \pmod{10}$ 。比如 $n=5$ 时， $s_0$ 就是 "01234"。
之后的字符串 $s_{i+1}$ 是由 $s_i$ 修改一个字符得到的。具体来说，我们会得到一个 $0$ 到 $n-1$ 的排列 $p$ 和一个数字序列 $d$ 。从 $s_i$ 变成 $s_{i+1}$ ，就是把 $s_i$ 的第 $p[i]$ 个字符换成 $d[i]$ 。这个过程会进行 $n$ 次（ $i$ 从 $0$ 到 $n-1$ ）。

我们的任务是把这 $n+1$ 个字符串 $s_0, s_1, \ldots, s_n$ 进行字典序排序。排序规则是：

如果字符串 $s_i$ 的字典序小于 $s_j$ ，那么 $s_i$ 就排在 $s_j$ 前面。
如果两个字符串完全一样（ $s_i = s_j$ ），那么下标小的那个排在前面（即 $i < j$ ）。

排序后，每个字符串 $s_i$ 都会有一个新的位置，我们称之为它的排名（rank），从 0 开始计数。设 $s_i$ 的排名为 $r_i$ 。

最后，我们需要计算所有排名的哈希值： $\left(\sum_{i=0}^{n} r_i \cdot H^i\right) \pmod{M}$ ，其中 $H = 10000019$ ， $M = 10^9 + 7$ 。

题目中的排列 $p$ 和数字序列 $d$ 是通过给定的种子和线性同余方程生成的，我们需要先自己生成它们哦，喵~

解题思路分析

这道题的 $n$ 非常大，可以达到 $2 \cdot 10^6$ 。如果我们真的把所有 $n+1$ 个字符串都生成出来，再用 std::sort 去排序，那时间和空间都会爆炸的，喵！所以我们必须找到一个更聪明的办法，不需要显式地构建字符串就能比较它们。

关键洞察：如何比较两个字符串？

让我们来想想怎么比较任意两个字符串 $s_i$ 和 $s_j$ （假设 $i < j$ ）。

字符串 $s_i$ 是由 $s_0$ 经过 $i$ 次修改（在 $p[0], p[1], \ldots, p[i-1]$ 位置）得到的。字符串 $s_j$ 是由 $s_0$ 经过 $j$ 次修改（在 $p[0], p[1], \ldots, p[j-1]$ 位置）得到的。

它们俩都经历了 $p[0]$ 到 $p[i-1]$ 的修改，所以在这些位置上的修改历史是一样的。它们的不同之处，在于 $s_j$ 还额外经历了 $p[i], p[i+1], \ldots, p[j-1]$ 的修改。

要比较 $s_i$ 和 $s_j$ 的字典序，我们只需要找到它们第一个不同的字符位置。这个位置在哪里呢？它一定是在 $p[i], \ldots, p[j-1]$ 这些修改位置中，下标最小的那个！设这个最小的下标是 $p_{min} = \min_{k=i}^{j-1} \{p[k]\}$ ，并且这个最小值是在第 $k_0$ 步修改时出现的（即 $p[k_0] = p_{min}$ ）。

在 $p_{min}$ 这个位置上， $s_i$ 的字符是什么呢？因为所有在 $[i, j-1]$ 范围内的修改位置都 $\ge p_{min}$ ，所以 $s_i$ 在 $p_{min}$ 位置的字符没有被修改过，还是它最初始的样子，也就是 $p_{min} \pmod{10}$ 。
在 $p_{min}$ 这个位置上， $s_j$ 的字符是什么呢？它已经被第 $k_0$ 步的修改变成了 $d[k_0]$ 。
对于任何比 $p_{min}$ 更小的位置，因为在 $[i, j-1]$ 范围内没有修改发生，所以 $s_i$ 和 $s_j$ 在这些位置上的字符是完全一样的。

所以， $s_i$ 和 $s_j$ 的大小关系，就完全由它们在 $p_{min}$ 位置上的字符决定了！

如果 $p_{min} \pmod{10} < d[k_0]$ ，那么 $s_i < s_j$ 。
如果 $p_{min} \pmod{10} > d[k_0]$ ，那么 $s_i > s_j$ 。
如果相等呢？那说明第 $k_0$ 步的修改没有改变字符串内容。我们就得在 $[i, j-1]$ 中找下一个最小的 $p[k]$ 来比较。

笛卡尔树的登场！

这种“区间最小值决定一切”的结构，是不是让你想到了什么？对啦！就是笛卡尔树 (Cartesian Tree)，喵~

我们可以把修改步骤的序列 $0, 1, \ldots, n-1$ 看作是笛卡尔树的键（key），而对应的值（value）就是 $p[0], p[1], \ldots, p[n-1]$ 。笛卡尔树的每个节点，既满足二叉搜索树的性质（对键而言），也满足堆的性质（对值而言）。在这里，我们让它满足小根堆的性质。

也就是说，对于任意一个子树，树根对应的值 $p[k]$ 是这棵子树所有节点中最小的。

这棵树有什么用呢？树中的一个节点 $k$ （代表第 $k$ 步修改），把它的父节点所代表的字符串区间，分成了两部分：

左子树代表的修改步骤，发生在 $k$ 之前。
右子树代表的修改步骤，发生在 $k$ 之后。而节点 $k$ 本身，就是连接这两部分的关键。

更重要的是，这个节点 $k$ 把字符串序列 $s_0, \ldots, s_n$ 也分成了两部分： $\{s_0, \ldots, s_k\}$ 和 $\{s_{k+1}, \ldots, s_n\}$ 。根据我们刚才的分析，这两个集合整体的先后顺序，就由第 $k$ 步修改决定！

如果 $p[k] \pmod{10} < d[k]$ ，那么 $\{s_0, \ldots, s_k\}$ 这个集合里的所有字符串，都排在 $\{s_{k+1}, \ldots, s_n\}$ 集合的前面。
如果 $p[k] \pmod{10} > d[k]$ ，反之亦然。

这样，整个排序问题就变成了一个在笛卡尔树上进行递归（DFS）的问题了！

一个小优化：如果某一步修改 $p[k] \pmod{10} == d[k]$ ，那么 $s_k = s_{k+1}$ 。这次修改对字典序没有任何影响，我们可以忽略它。所以，我们只对那些真正产生变化的修改步骤来构建笛卡尔树。

差分数组的魔法

我们可以在笛卡尔树上DFS，来确定每个字符串的最终排名。但直接递归传递排名信息有点麻烦。这里有一个更优雅的技巧：差分数组！

我们可以创建一个差分数组 rank_diff，大小为 $n+2$ 。我们用它来记录每个字符串排名的增量。

当我们DFS到笛卡尔树的节点 $k$ 时，假设它负责排序字符串区间 $[L, R]$ 。节点 $k$ 会把这个区间分成 $[L, k]$ 和 $[k+1, R]$ 。

如果 $\{s_L, \ldots, s_k\}$ 排在前面，那么 $\{s_{k+1}, \ldots, s_R\}$ 里的所有字符串，它们的排名都要整体增加 $\{s_L, \ldots, s_k\}$ 的数量，也就是 $k - L + 1$ 。我们可以在差分数组上做两次操作来记录这个整体的增加：rank_diff[k+1] += (k-L+1) 和 rank_diff[R+1] -= (k-L+1)。
如果 $\{s_{k+1}, \ldots, s_R\}$ 排在前面，那么 $\{s_L, \ldots, s_k\}$ 里的所有字符串，它们的排名都要整体增加 $\{s_{k+1}, \ldots, s_R\}$ 的数量，也就是 $R - k$ 。同样地，rank_diff[L] += (R-k) 和 rank_diff[k+1] -= (R-k)。

等我们DFS遍历完整个笛卡尔树，对 rank_diff 数组求一遍前缀和，rank_diff[i] 就变成了 $s_i$ 的初步排名。

最后的冲刺：处理平局

这个初步排名有一个问题：如果多个字符串是完全相同的，它们的初步排名也会是一样的。但题目要求，相同的字符串要按照原始下标 $i$ 的大小来排序。

这正是稳定排序的用武之地！我们已经有了每个字符串的初步排名，我们可以用这个初步排名作为键，对字符串的原始下标 $0, 1, \ldots, n$ 进行一次稳定排序。

计数排序是这里最完美的工具。因为排名是从 $0$ 到 $n$ 的整数，非常适合计数排序。

统计每个初步排名出现的次数。
计算每个排名对应在最终排好序的数组中的起始位置（通过前缀和）。
遍历原始下标 $0, \ldots, n$ ，根据它们的初步排名，把它们放到最终位置上。为了保证稳定性，我们通常倒序遍历。
这样我们就得到了一个 final_pos 数组，final_pos[j] = i 表示最终排在第 $j$ 位的字符串是 $s_i$ 。
最后，我们再反过来计算每个 $s_i$ 的最终排名 $r_i$ ：r[final_pos[j]] = j。

搞定！有了所有 $r_i$ ，我们就可以计算最终的哈希值啦，喵~

总结一下步骤：

生成排列 p 和数字 d。
筛选出所有会引起字符串变化的修改步骤 $k$ (即 $p[k] \pmod{10} \ne d[k]$ )。
用这些步骤的 $p[k]$ 值，构建一个笛卡尔树。
在笛卡尔树上DFS，用差分数组计算每个字符串的初步排名。
对差分数组求前缀和。
使用计数排序，根据初步排名和原始下标，计算出最终的稳定排名 $r_i$ 。
计算哈希值并输出。

代码实现

cpp

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

// 使用快读快写，对付大数据量是必须的喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
}

// 笛卡尔树的节点，k是修改步骤的下标
struct Node {
    int p_val; // p[k] 的值
    int d_val; // d[k] 的值
    int left = -1, right = -1; // 左右子节点的下标
};

std::vector<Node> tree;
std::vector<int> influential_indices; // 存放有影响的修改步骤k
std::vector<long long> rank_diff;

// 在笛卡尔树上DFS，用差分数组计算排名
void solve_ranks_dfs(int k_idx, int L, int R) {
    if (k_idx == -1) {
        // 这个区间内没有产生影响的修改，所有字符串都一样
        // 他们的相对顺序就是原始下标顺序，我们什么都不用做
        // 初始排名为0，后续的稳定排序会处理好
        return;
    }

    int k = influential_indices[k_idx];
    const auto& node = tree[k_idx];

    // 比较 p[k]%10 和 d[k]
    if ((node.p_val % 10) < node.d_val) {
        // 左边部分 {s_L, ..., s_k} 在前
        // 右边部分 {s_{k+1}, ..., s_R} 的排名需要整体增加
        // 增加的数量是左边部分的字符串数量：k - L + 1
        if (k + 1 <= R) {
            rank_diff[k + 1] += (k - L + 1);
            if (R + 1 <= tree.size()) {
                rank_diff[R + 1] -= (k - L + 1);
            }
        }
        solve_ranks_dfs(node.left, L, k);
        solve_ranks_dfs(node.right, k + 1, R);
    } else {
        // 右边部分 {s_{k+1}, ..., s_R} 在前
        // 左边部分 {s_L, ..., s_k} 的排名需要整体增加
        // 增加的数量是右边部分的字符串数量：R - k
        if (L <= k) {
            rank_diff[L] += (R - k);
            if (k + 1 <= tree.size()) {
                rank_diff[k + 1] -= (R - k);
            }
        }
        solve_ranks_dfs(node.right, k + 1, R);
        solve_ranks_dfs(node.left, L, k);
    }
}


void solve() {
    int n;
    std::cin >> n;

    long long p_seed, p_A, p_B, p_mod;
    std::cin >> p_seed >> p_A >> p_B >> p_mod;
    long long d_seed, d_A, d_B, d_mod;
    std::cin >> d_seed >> d_A >> d_B >> d_mod;

    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    for (int i = 1; i < n; ++i) {
        std::swap(p[i], p[p_seed % (i + 1)]);
        p_seed = (p_seed * p_A + p_B) % p_mod;
    }

    std::vector<int> d(n);
    for (int i = 0; i < n; ++i) {
        d[i] = d_seed % 10;
        d_seed = (d_seed * d_A + d_B) % d_mod;
    }

    // 筛选出有影响的修改步骤
    influential_indices.clear();
    for (int i = 0; i < n; ++i) {
        if ((p[i] % 10) != d[i]) {
            influential_indices.push_back(i);
        }
    }

    if (influential_indices.empty()) {
        // 所有字符串都和s0一样，排名就是原始下标
        // 这种情况很简单，直接计算哈希值
        long long final_hash = 0;
        long long hash_power = 1;
        long long H = 10000019;
        long long M = 1e9 + 7;
        for (int i = 0; i <= n; ++i) {
            final_hash = (final_hash + (long long)i * hash_power) % M;
            hash_power = (hash_power * H) % M;
        }
        std::cout << final_hash << "\n";
        return;
    }

    int m = influential_indices.size();
    tree.assign(m, Node{});
    for(int i = 0; i < m; ++i) {
        int k = influential_indices[i];
        tree[i].p_val = p[k];
        tree[i].d_val = d[k];
    }
    
    // O(N) 构建笛卡尔树
    std::vector<int> st; // 栈里存的是在 tree 数组里的下标
    for (int i = 0; i < m; ++i) {
        int last_popped = -1;
        while (!st.empty() && tree[st.back()].p_val > tree[i].p_val) {
            last_popped = st.back();
            st.pop_back();
        }
        if (last_popped != -1) {
            tree[i].left = last_popped;
        }
        if (!st.empty()) {
            tree[st.back()].right = i;
        }
        st.push_back(i);
    }
    int root_idx = st[0];

    // DFS + 差分数组计算初步排名
    rank_diff.assign(n + 2, 0);
    solve_ranks_dfs(root_idx, 0, n);

    // 计算前缀和得到初步排名
    std::vector<long long> preliminary_ranks(n + 1);
    preliminary_ranks[0] = rank_diff[0];
    for (int i = 1; i <= n; ++i) {
        preliminary_ranks[i] = preliminary_ranks[i - 1] + rank_diff[i];
    }

    // 使用计数排序处理平局，得到最终排名
    std::vector<int> rank_counts(n + 1, 0);
    for (int i = 0; i <= n; ++i) {
        rank_counts[preliminary_ranks[i]]++;
    }
    for (int i = 1; i <= n; ++i) {
        rank_counts[i] += rank_counts[i - 1];
    }

    std::vector<int> final_indices(n + 1);
    for (int i = n; i >= 0; --i) {
        final_indices[--rank_counts[preliminary_ranks[i]]] = i;
    }

    std::vector<int> final_ranks(n + 1);
    for (int i = 0; i <= n; ++i) {
        final_ranks[final_indices[i]] = i;
    }

    // 计算哈希值
    long long final_hash = 0;
    long long hash_power = 1;
    long long H = 10000019;
    long long M = 1e9 + 7;

    for (int i = 0; i <= n; ++i) {
        final_hash = (final_hash + (long long)final_ranks[i] * hash_power) % M;
        hash_power = (hash_power * H) % M;
    }
    std::cout << final_hash << "\n";
}

int main() {
    fast_io();
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(N)$
- 生成排列 p 和数字 d 需要 $O(N)$ 的时间。
- 筛选有影响的修改步骤，遍历一次，也是 $O(N)$ 。
- 使用栈构建笛卡尔树，每个元素入栈出栈一次，复杂度是 $O(M)$ ，其中 $M \le N$ 是有影响的步骤数。所以是 $O(N)$ 。
- DFS 遍历笛卡尔树，每个节点访问一次，复杂度是 $O(M)$ ，也就是 $O(N)$ 。
- 对差分数组求前缀和，需要 $O(N)$ 。
- 最后的计数排序，包括统计、求前缀和、填充，都是 $O(N)$ 。
- 计算哈希值也是 $O(N)$ 。
- 所以总的时间复杂度就是线性的 $O(N)$ ，非常高效，喵~
空间复杂度: $O(N)$
- 我们需要存储 p 和 d 数组，空间 $O(N)$ 。
- 存储有影响的修改步骤 influential_indices，最坏情况是 $O(N)$ 。
- 笛卡尔树 tree 数组，最坏情况是 $O(N)$ 。
- 差分数组 rank_diff 和各种排名数组，都是 $O(N)$ 。
- 总的空间复杂度也是 $O(N)$ 。

知识点总结

这道题是一道非常巧妙的数据结构题，将好几个知识点串联了起来，像一串美味的鱼干，喵~

问题转化: 核心是把复杂的字符串比较问题，转化为寻找区间最小值的问题。这是解题的第一步，也是最关键的一步。
笛卡尔树: 对于“区间最小值决定一切”的结构，笛卡尔树是天然的解决方案。它能把区间的递归关系，用一个清晰的树形结构表示出来，让我们可以在上面进行高效的遍历。
差分数组: 差分数组是处理“对一个区间进行统一加减”操作的利器。通过在差分数组上进行两次单点修改，就能实现对一个区间的批量操作，最后通过一次前缀和还原出结果，大大提高了效率。
稳定排序/计数排序: 当需要根据一个主键排序，但主键相同时又要保持原有顺序，就需要稳定排序。计数排序是一种非常高效的稳定排序算法，特别适合用在键是小范围整数的场景。
伪随机数生成: 题目中数据的生成方式是线性同余法，这是竞赛中常见的数据生成方式，需要熟悉并正确实现。

通过这道题，我们可以学到如何分析问题的内在结构，并用合适的数据结构（笛卡尔树）来建模，再结合算法技巧（差分、计数排序）来高效地解决问题。真是充满挑战又乐趣无穷的一道题呀，喵~

SorttheStringsRevision - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键洞察：如何比较两个字符串？ ​

笛卡尔树的登场！ ​

差分数组的魔法 ​

最后的冲刺：处理平局 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​