E. A Simple Task - 题解

比赛与标签

比赛: Codeforces Round 312 (Div. 2) 标签: data structures, sortings, strings 难度: *2300

题目大意喵~

主人 sama，你好呀！这道题的任务其实很简单哦~

我们有一个长度为 n 的字符串 S，只包含小写英文字母。接下来会有 q 次操作。每次操作会给你三个数字 i, j, k。

• 如果 k = 1，我们就需要把字符串 S 从第 i 个位置到第 j 个位置的子串，按照字母表顺序（a, b, c...）进行升序排序。
• 如果 k = 0，我们就需要把这个子串，按照字母表逆序（z, y, x...）进行降序排序。

在完成所有 q 次操作后，我们需要输出最终的字符串 S 的样子。很简单对吧？喵~

解题思路分析呐

看到这种对一个区间的子串进行修改和查询的操作，主人 sama 是不是立刻就想到了我们强大的线段树呢？没错喵！这道题就是一个非常经典的线段树应用题。

如果每次查询都真的去提取子串、排序、再放回去，那对于 n 和 q 都很大的情况，肯定会超时啦 (TLE 的说)！所以我们需要一个更高效的方法。

核心思想转换

排序的本质是什么呢？其实就是统计区间内每个字符出现的次数，然后按照指定的顺序重新排列！

比如说，我们要对子串 abacd 进行升序排序。

1. 我们先数一下：'a' 出现了2次，'b' 出现了1次，'c' 出现了1次，'d' 出现了1次。
2. 然后按升序把它们放回去：先放2个'a'，再放1个'b'，再放1个'c'，最后放1个'd'。子串就变成了 aabcd。

看吧，问题就转换成了两个操作：

1. 区间查询：高效地查询出任意区间 [i, j] 内，'a' 到 'z' 这26个字母分别出现了多少次。
2. 区间更新：根据查询到的字符数量，按顺序将它们写回原区间。比如，先把一段区间全变成 'a'，紧接着的一段全变成 'b'，以此类推。

线段树的设计

为了实现上面的操作，我们可以设计一棵特别的线段树，喵~

1. 节点信息：线段树的每个节点，不再是只存一个简单的和或者最大值。我们需要它存储一个长度为26的数组 cnt[26]，其中 cnt[i] 代表这个节点所管辖的区间内，第 i 个字母（'a'+i）出现的总次数。

2. 懒惰标记 (Lazy Propagation)：为了实现高效的区间更新（比如把一段区间 [x, y] 全都改成字符 c），懒惰标记是必不可少的！我们给每个节点增加一个 lazy 标记。

   • lazy = -1 (或者其他特殊值) 表示没有懒惰标记。
   • lazy = c (其中 0 <= c < 26) 表示这个节点对应的整个区间，都等待被更新为字符 'a' + c。

操作流程

现在我们来看看具体的操作流程是怎样的：

1. 建树 (Build)： 我们从根节点开始，递归地构建线段树。对于每个叶子节点，它代表字符串中的一个字符。比如说，第 i 个位置的字符是 s[i]，那么这个叶子节点的 cnt[s[i]-'a'] 就是1，其他的 cnt 都是0。父节点的 cnt 数组就是它左右子节点的 cnt 数组对应位相加的结果。

2. 处理一次查询 (i, j, k)： a. 查询字符数：首先，我们在线段树上进行一次区间查询，范围是 [i, j]。这次查询会返回一个 freq[26] 数组，告诉我们这个子串里'a'到'z'分别有多少个。 b. 重新写回：接下来就是最关键的一步！我们根据 k 的值（升序或降序）和 freq 数组，来更新 [i, j] 这段区间。

   • 升序 (k=1)：我们从 'a' 开始遍历到 'z'。
     • 假设'a'有 freq[0] 个，我们就在线段树上执行一次区间更新，把 [i, i + freq[0] - 1] 这个范围全部更新成 'a'。
     • 接着，假设'b'有 freq[1] 个，我们再更新 [i + freq[0], i + freq[0] + freq[1] - 1] 这个范围，全部更新成 'b'。
     • ...以此类推，直到所有字符都放回去。
   • 降序 (k=0)：逻辑完全一样，只是我们从 'z' 遍历到 'a' 就好啦。

3. 输出最终结果： 当所有 q 次操作都完成后，线段树里就保存了最终字符串的状态。我们只需要从根节点开始，一路 push_down 所有懒惰标记直到叶子节点，然后根据每个叶子节点的 cnt 数组（此时只有一个值为1），就能确定该位置最终的字符是什么了，然后把它们拼起来就是答案啦！

这样一来，每次操作的复杂度都和 log n 相关，整体效率就高多啦！

代码实现喵~

这是完整的AC代码，人家已经加上了详细的注释，方便主人 sama 理解哦~

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

// 字母表大小，喵~
const int A = 26;

// 线段树节点结构体
struct Node {
    int cnt[A]; // 存储区间内 a-z 各字符的数量
    int lazy;   // 懒惰标记, -1表示无标记, 0-25表示要更新为哪个字符
};

vector<Node> tree; // 线段树本体
string s;          // 原始字符串

// push_down 操作，将父节点的懒惰标记下传给子节点
void push(int node, int l, int r) {
    // 如果当前节点没有懒惰标记，就什么都不做
    if (tree[node].lazy != -1) {
        int letter = tree[node].lazy; // 要更新成的字符
        int len = r - l + 1;          // 区间长度

        // 更新当前节点的cnt数组
        for (int i = 0; i < A; i++) {
            tree[node].cnt[i] = 0;
        }
        tree[node].cnt[letter] = len;

        // 如果不是叶子节点，把懒惰标记传给孩子们
        if (l != r) {
            tree[node*2].lazy = letter;
            tree[node*2+1].lazy = letter;
        }

        // 清除当前节点的懒惰标记
        tree[node].lazy = -1;
    }
}

// 建树操作
void build(int node, int l, int r) {
    tree[node].lazy = -1; // 初始化懒惰标记
    if (l == r) { // 到达叶子节点
        for (int i = 0; i < A; i++) {
            tree[node].cnt[i] = 0;
        }
        int c = s[l] - 'a';
        tree[node].cnt[c] = 1; // 对应字符计数为1
        return;
    }
    int mid = (l + r) / 2;
    build(node*2, l, mid);
    build(node*2+1, mid+1, r);
    // push_up: 父节点的cnt是左右孩子cnt之和
    for (int i = 0; i < A; i++) {
        tree[node].cnt[i] = tree[node*2].cnt[i] + tree[node*2+1].cnt[i];
    }
}

// 区间更新：将[ql, qr]范围内的字符全部更新为 letter
void update_range(int node, int l, int r, int ql, int qr, int letter) {
    push(node, l, r); // 先处理懒惰标记
    if (qr < l || r < ql) { // 查询区间与当前区间无交集
        return;
    }
    if (ql <= l && r <= qr) { // 查询区间完全覆盖当前区间
        tree[node].lazy = letter; // 打上懒惰标记
        push(node, l, r);         // 立即更新当前节点并准备下传
        return;
    }
    int mid = (l + r) / 2;
    update_range(node*2, l, mid, ql, qr, letter);
    update_range(node*2+1, mid+1, r, ql, qr, letter);
    // 更新完孩子后，也要更新自己
    for (int i = 0; i < A; i++) {
        tree[node].cnt[i] = tree[node*2].cnt[i] + tree[node*2+1].cnt[i];
    }
}

// 区间查询：查询[ql, qr]范围内的各字符数量，结果累加到res数组中
void query_range(int node, int l, int r, int ql, int qr, int* res) {
    push(node, l, r); // 先处理懒惰标记
    if (qr < l || r < ql) { // 无交集
        return;
    }
    if (ql <= l && r <= qr) { // 完全覆盖
        for (int i = 0; i < A; i++) {
            res[i] += tree[node].cnt[i];
        }
        return;
    }
    int mid = (l + r) / 2;
    query_range(node*2, l, mid, ql, qr, res);
    query_range(node*2+1, mid+1, r, ql, qr, res);
}

// 最终构建字符串
void build_string(int node, int l, int r, string& res) {
    push(node, l, r); // 把所有懒惰标记都推到叶子节点
    if (l == r) { // 到达叶子节点
        for (int i = 0; i < A; i++) {
            if (tree[node].cnt[i] > 0) { // 找到计数值为1的那个字符
                res[l] = 'a' + i;
                break;
            }
        }
        return;
    }
    int mid = (l + r) / 2;
    build_string(node*2, l, mid, res);
    build_string(node*2+1, mid+1, r, res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    cin >> s;

    tree.resize(4 * n);
    build(1, 0, n-1); // 建立线段树，下标从0开始

    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        l--; r--; // 转换为0-based index

        int freq[A] = {0}; // 临时数组存字符频率
        query_range(1, 0, n-1, l, r, freq);

        if (k == 1) { // 升序
            int start = l;
            for (int c = 0; c < A; c++) { // 从 'a' 到 'z'
                if (freq[c] > 0) {
                    // 将这个字符写回对应区间
                    update_range(1, 0, n-1, start, start + freq[c] - 1, c);
                    start += freq[c];
                }
            }
        } else { // 降序
            int start = l;
            for (int c = A-1; c >= 0; c--) { // 从 'z' 到 'a'
                if (freq[c] > 0) {
                    // 将这个字符写回对应区间
                    update_range(1, 0, n-1, start, start + freq[c] - 1, c);
                    start += freq[c];
                }
            }
        }
    }

    string res(n, ' ');
    build_string(1, 0, n-1, res); // 从线段树恢复最终字符串
    cout << res << endl;

    return 0;
}

复杂度分析

• 时间复杂度: O(q * A * A * log n) 的说。
  • 建树: O(n * A)，因为每个节点需要初始化一个大小为A的数组。
  • 每次查询:
    • 查询字符数 query_range: 每次递归调用，合并或下推懒惰标记都需要 O(A) 的时间，树高是 O(log n)，所以一次区间查询是 O(A * log n)。
    • 更新区间: 在最坏情况下，一个子串可能包含所有26种字符。这意味着我们需要调用 update_range 函数最多 A 次。每次 update_range 的复杂度也是 O(A * log n)。所以更新部分的总复杂度是 O(A * A * log n)。
    • 单次总和: O(A log n + A^2 log n) = O(A^2 log n)。
  • 总时间复杂度: O(n * A + q * A^2 * log n)。这里的 A 是常数26。虽然理论上看起来有点高，但因为这道题给了5秒的超长时限，所以这个解法是可以通过的哦！
• 空间复杂度: O(n * A) 的说。
  • 线段树需要大约 4n 个节点，每个节点存储一个大小为 A 的数组，所以空间复杂度是 O(n * A)。

知识点与总结

这道题真是一次很棒的线段树练习呢，喵~

1. 问题转换能力: 核心在于将 "区间排序" 操作，巧妙地转换为了 "区间字符计数" + "分段区间覆盖" 操作。这是解决复杂问题的常用思路！
2. 线段树的灵活应用: 我们不能死板地认为线段树节点只能存一个数。根据问题需要，节点可以存储数组、结构体等任何需要的信息。在这里，cnt[26] 数组就是关键。
3. 懒惰标记的威力: 对于区间更新问题，懒惰标记是降维打击！它能把 O(n) 的朴素更新优化到 O(log n) 级别。
4. 最终状态的获取: 当所有操作结束后，信息都储存在线段树里。通过一次最终的遍历（比如 build_string 函数），我们就能将树中分散的信息整合起来，得到最终答案。

希望这篇题解能帮助到主人 sama！如果还有不明白的地方，随时可以再来问我哦！一起加油，攻克更多有趣的算法题吧！喵~ >w<