字符串排序

GitHub跳转原题关系图返回列表

把串切成同字母的连续段,每次排序先二分定位区间内的段、统计 26 个字母的计数,再按升/降序整段铺回,段数均摊 O(n+26m)。

OJ: roj

题目 ID: 1751

难度:提高+/省选-

标签:数据结构线段树区间赋值python

创建: 2026-10-07 21:10

更新: 2026-10-07 21:10

形式化题目

给定长度为 nn 的小写字母串 S=S1S2⋯SnS = S_1 S_2 \cdots S_n,依次执行 mm 次操作。 每次操作给出 l,r,xl, r, x(1⩽l⩽r⩽n1 \leqslant l \leqslant r \leqslant n,x∈{0,1}x \in \{0, 1\}):

  • x=1x = 1:把子串 Sl⋯SrS_l \cdots S_r 升序排序;
  • x=0x = 0:把子串 Sl⋯SrS_l \cdots S_r 降序排序。

排序会覆盖原来的字符,后续操作看到的是上一步的结果。求全部操作结束后的完整字符串。

n,m⩽105n, m \leqslant 10^5,其中 40%40\% 的数据 n,m⩽103n, m \leqslant 10^3;串只含小写字母。

输入顺序的坑。 题面散文写"接下来 mm 行每行三个整数 x,l,rx, l, r", 但【输入样例】两行是 1 3 1 和 3 5 0, 只有按 (l,r,x)(l, r, x) 解释才能得到样例输出: l=1,r=3l=1, r=3 升序把 cab 排成 abc,l=3,r=5l=3, r=5 降序把 ccd 排成 dcc, 全串变成 abdcc。若按 (x,l,r)(x, l, r) 解释,第一行就要求 l=3>r=1l=3 > r=1,非法。 因此本题实际输入顺序是 l r xl\ r\ x,正文以下的推导都按这个顺序。

本题与 Codeforces 558E “A Simple Task” 同源:题面、样例、数据范围(40%40\% 时 n,m⩽103n,m \leqslant 10^3,100%100\% 时 n,m⩽105n,m \leqslant 10^5)逐项一致。

样例的逐步过程:

步骤 串 说明
初始 c a b c d
l=1,r=3,x=1l=1, r=3, x=1 a b c c d cab 升序 → abc
l=3,r=5,x=0l=3, r=5, x=0 a b d c c ccd 降序 → dcc

正解

思路

先看朴素做法的瓶颈。 最直接的做法是每次把区间内的字符取出来排序再写回: S[l:r+1] = sorted(S[l:r+1]),单次 O((r−l+1)log⁡(r−l+1))O((r-l+1)\log(r-l+1)), 最坏(每次都排整串)O(nmlog⁡n)O(nm\log n),n=m=105n = m = 10^5 时是 101010^{10} 量级,必然超时。 瓶颈非常清楚:一次排序只关心 26 个字母各有多少个,却被展开成了对每个位置的单独搬运。

关键观察:排序的输入只需要"计数"。 一次排序 (l,r,x)(l, r, x) 的输出是确定的, 只要知道 cnt_c = $(c$ 在 [l,r][l, r] 中的出现次数),c=0…25c = 0 \dots 25, 结果就是"把 cnt0cnt_0 个 a、cnt1cnt_1 个 b……按顺序连续摆放": x=1x = 1 时 a 在最左、z 在最右,x=0x = 0 时反过来。每个位置只属于一个字母, 所以 cntcnt 是对区间长度的一个划分,不会有重叠或遗漏。

于是真正需要维护的只有两件事:区间内 26 个字母的计数,和区间被整段覆盖成某个字母。 这两个需求正是"区间求和 + 区间赋值",线段树(或树状数组 + 并查集)能办。

两种实现路线。

路线 维护什么 单次操作代价
计数型(main.cpp) 26 棵线段树,第 cc 棵的位置 ii 为 1 当且仅当 Si=cS_i = c O(26log⁡n)O(26 \log n)
段型 / ODT(main.py) 直接维护"同字母的连续段"列表 均摊 O(26log⁡n)O(26 \log n),常数小

计数型(main.cpp)。 每个字母 cc 一棵线段树,维护 0/1 序列 “SiS_i 是不是 cc”。一次操作分三步:

  1. 对 c=0…25c = 0 \dots 25 求出 cnt_c = $ 第 $c 棵树的区间和;
  2. 把 [l,r][l, r] 中出现过的字母整段清零(cntc>0cnt_c > 0 的那些)。 这一步不能省:26 棵树彼此独立,"给 a 树赋值"不会顺手清掉 b 树里的旧标记, 残留字符会和新的区间划分冲突;
  3. 从 pos=lpos = l 出发,x=1x = 1 时 cc 从 0 枚举到 25,x=0x = 0 时从 25 枚举到 0, 对每个 cntc>0cnt_c > 0 的字母把 [pos,pos+cntc−1][pos, pos + cnt_c - 1] 整段赋值成 1,pospos 右移。

区间赋值需要懒标记:整段被覆盖成常量后,该节点的和可以直接算出, 直到下一次需要下探才把标记推给孩子。这样单次操作 O(26log⁡n)O(26 \log n),总 O((n+78m)log⁡n)O((n + 78m)\log n)。

段型 / ODT(main.py)。 换个更贴合题意的表示:把整串切成若干同字母的连续段, 只存每段的起点和字母。例如 cabcd 是 5 段,而样例第一次排序后 abccd 只有 4 段。 一次排序 (l,r,x)(l, r, x) 要读的"区间内 26 个字母的计数"就是这个段列表上的一段切片:

  1. 先按 ll 与 r+1r + 1 把边界切开(二分找到落点,必要时把一段拆成两段), 这样区间 [l,r][l, r] 恰好由若干完整段拼成;
  2. 累加这些段的长度得到 cntcnt;
  3. 删掉这些段,按 xx 的顺序用 cntcnt 重建最多 26 个新段; 首尾与区间外同字母的邻段合并,避免段数虚增。

段数不会爆:初始最多 nn 段,每次操作最多新增 26 段,而被删除的段不会再回来, 所以"删除的总量"被"新增的总量" O(n+26m)O(n + 26m) 兜住 —— 这就是为什么它虽然看着是暴力, 复杂度却是均摊正确的。它和线段树路线同阶,而且免去了懒标记、下传和递归, 在 Python 里常数小得多。

为什么两个版本都写? 本题的 data/ 由 data.py 生成、标程是 26 棵线段树的版本, 顶格数据 n=m=105n = m = 10^5。main.cpp 直接对应"区间求和 + 区间赋值"的线段树主线, main.py 用同一套计数思想换一个更省常数的表示,两条路线互为对照。

关于素材源。 new_ROJ/problems/1751/ 同时带着 data.py(数据生成脚本)与 std.cpp。这说明 data/ 是自造的(生成脚本已注明分层与随机种子), 题面则是按 CF558E 重建的。std.cpp 的输入顺序读作 l r x,与样例互证, 与 data.py 一致;本解按同一顺序读入,实测 10 个测试点全部与 .out 吻合。 官方原题的出题意图可能与这份重建题面有细微出入,但算法主线不受影响。

代码

Python 版(段型 / ODT,用 bisect 定位段边界;只需标准库):

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 21:10
# update_at: 2026-10-07 21:10

import sys
from bisect import bisect_right

ALPHA = 26  # 字母表大小:字母编号 0..25 对应 a..z

type Runs = list[list[int]]  # 连续段列表:一段是 [起点, 字母编号],按起点严格递增

# 段列表不记终点:第 i 段的终点是下一段的起点减一,最后一段延伸到 n。
# 用 [pos, ALPHA] 当二分键可以定位「起点 <= pos 的最后一段」(字母编号都 < ALPHA)。


def split_at(runs: Runs, pos: int) -> None:
    """让 pos 成为某一段的起点:pos 落在段内部时,从 pos 处补一段同字母的尾巴。"""
    i = bisect_right(runs, [pos, ALPHA]) - 1
    if runs[i][0] != pos:
        runs.insert(i + 1, [pos, runs[i][1]])


def sort_range(runs: Runs, n: int, l: int, r: int, ascending: int) -> None:
    """把 [l, r] 按升序 / 降序重排。

    区间内每个位置恰好属于一个字母,所以只要知道 26 个字母各有多少个,
    就能按顺序把它们的计数整段铺回;区间外的段完全不动。
    每次操作最多新建 26 段、删掉的段不会再回来,段数因此是均摊有界的。
    """
    split_at(runs, l)
    if r < n:
        split_at(runs, r + 1)  # 让 r+1 也成为段起点,区间内的段才连成整片
    a = bisect_right(runs, [l, ALPHA]) - 1  # 区间左端所在段的下标
    b = bisect_right(runs, [r, ALPHA]) - 1  # 区间右端所在段的下标

    cnt = [0] * ALPHA
    for i in range(a, b + 1):
        end = runs[i + 1][0] if i + 1 < len(runs) else n + 1
        cnt[runs[i][1]] += end - runs[i][0]

    order = range(ALPHA) if ascending else range(ALPHA - 1, -1, -1)
    pos = l
    fresh: Runs = []
    for c in order:  # 出现次数为 0 的字母不产生段
        if cnt[c]:
            fresh.append([pos, c])
            pos += cnt[c]

    # 首尾与区间外同字母的邻段相接时把邻居一起纳入替换范围,段数才不会虚增。
    # 左邻居的起点在 l 之前,必须把 fresh[0] 的起点往回拉,否则会丢掉它覆盖的那一截。
    left_same = a > 0 and runs[a - 1][1] == fresh[0][1]
    if left_same:
        fresh[0][0] = runs[a - 1][0]
    # 右邻居的终点由 fresh 之后那一段的起点给出,吸收进 fresh[-1] 即可
    right_same = b + 1 < len(runs) and runs[b + 1][1] == fresh[-1][1]
    runs[a - left_same : b + 1 + right_same] = fresh


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    n, m = int(next(tokens)), int(next(tokens))
    s = next(tokens).decode()
    # 初始串只保留「字母变化处」作为段起点,最多 n 段
    runs: Runs = [[i, ord(ch) - 97] for i, ch in enumerate(s, 1) if i == 1 or ch != s[i - 2]]

    for _ in range(m):
        l = int(next(tokens))
        r = int(next(tokens))
        x = int(next(tokens))
        sort_range(runs, n, l, r, x)

    parts = []
    for i in range(len(runs)):
        end = runs[i + 1][0] if i + 1 < len(runs) else n + 1
        parts.append(chr(97 + runs[i][1]) * (end - runs[i][0]))
    print("".join(parts))


if __name__ == "__main__":
    solve()

C++ 版(26 棵线段树,区间求和 + 区间赋值):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 21:10
 * update_at: 2026-10-07 21:10
 *
 * 一本通 1751《字符串排序》(同源原题:Codeforces 558E A Simple Task)
 *
 * 题意:长度为 n 的小写字母串,m 次操作,每次把区间 [l, r] 升序或降序排序,求最终串。
 * 注意:题面散文写"每行三个整数 x,l,r",但输入样例 `1 3 1` / `3 5 0` 只有按 (l, r, x)
 *       解释才能得到样例输出 abdcc,故本题实际输入顺序为 l r x(数据生成脚本同此)。
 *
 * 算法:每个字母 c(0..25)维护一棵线段树,位置 i 上是 1 当且仅当 S_i == c。
 *   一次排序 (l, r, x):
 *     1) 对 c = 0..25 求 cnt[c] = 「c 在 [l, r] 中的个数」;
 *     2) 把 [l, r] 中所有出现过的字母(cnt[c] > 0)各自整段清零 —— 26 棵树彼此独立,
 *        赋值不会顺带清掉别的字母,必须先清;
 *     3) 按 x 决定字母顺序(升序 a→z,降序 z→a),把 cnt[c] 个 c 整段赋值回
 *        [pos, pos + cnt[c] - 1],pos 依次右移。
 *   cnt[] 是对 [l, r] 的一个划分,所以覆盖完成后区间内每个位置恰好属于一个字母。
 *
 * 复杂度:单次操作 26 次区间求和 + 最多 26 次区间清零 + 最多 26 次区间覆盖,
 *         即 O(26 log n);总 O((n + 78 m) log n),空间 O(26 n)。
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

ll n, m;             // n 为串长,m 为操作次数
char s[MAXN + 1];    // 题面给定的字符串,下标从 1 开始
char res[MAXN + 1];  // 最终答案串,下标从 1 开始

// 线段树节点:区间和 + 区间覆盖标记,聚合成 struct(避免平行数组)
struct SegNode {
    int sum;           // 该节点区间内「本树的字母」出现次数,不超过 n,用 int 省内存
    signed char lazy;  // -1 表示无覆盖标记;0 / 1 表示整段被覆盖成 0 / 1
};

// 字母 c 的线段树就是 tree[c];26 * 4n 个节点,值域只有 0/1
SegNode tree[26][4 * MAXN];

// 建树:叶子 i 为 1 当且仅当 s[i] == 'a' + c
void build(ll c, ll node, ll l, ll r) {
    tree[c][node].lazy = -1;
    if (l == r) {
        tree[c][node].sum = (s[l] - 'a' == c) ? 1 : 0;
        return;
    }
    ll mid = (l + r) >> 1;
    build(c, node << 1, l, mid);
    build(c, node << 1 | 1, mid + 1, r);
    tree[c][node].sum = tree[c][node << 1].sum + tree[c][node << 1 | 1].sum;
}

// 把节点 node 的整段 [l, r] 覆盖成 v(v = 0 或 1)
void apply(ll c, ll node, ll l, ll r, ll v) {
    tree[c][node].sum = v ? int(r - l + 1) : 0;
    tree[c][node].lazy = (signed char)v;
}

// 下传覆盖标记(叶子不需要下传)
void push_down(ll c, ll node, ll l, ll r) {
    if (tree[c][node].lazy == -1 || l == r) return;
    ll mid = (l + r) >> 1;
    ll v = tree[c][node].lazy;
    apply(c, node << 1, l, mid, v);
    apply(c, node << 1 | 1, mid + 1, r, v);
    tree[c][node].lazy = -1;
}

// 查询字母 c 在 [ql, qr] 中的出现次数
ll query(ll c, ll node, ll l, ll r, ll ql, ll qr) {
    if (ql <= l && r <= qr) return tree[c][node].sum;
    push_down(c, node, l, r);
    ll mid = (l + r) >> 1;
    ll tot = 0;
    if (ql <= mid) tot += query(c, node << 1, l, mid, ql, qr);
    if (qr > mid) tot += query(c, node << 1 | 1, mid + 1, r, ql, qr);
    return tot;
}

// 把 [ql, qr] 整段覆盖成 v(v = 0 表示这一段都不是字母 c,v = 1 表示都是)
void assign_range(ll c, ll node, ll l, ll r, ll ql, ll qr, ll v) {
    if (ql > qr) return;  // 空区间(某字母出现次数为 0 时可能被调用)
    if (ql <= l && r <= qr) {
        apply(c, node, l, r, v);
        return;
    }
    push_down(c, node, l, r);
    ll mid = (l + r) >> 1;
    if (ql <= mid) assign_range(c, node << 1, l, mid, ql, qr, v);
    if (qr > mid) assign_range(c, node << 1 | 1, mid + 1, r, ql, qr, v);
    tree[c][node].sum = tree[c][node << 1].sum + tree[c][node << 1 | 1].sum;
}

// 收集字母 c 出现的位置写入答案(整段为 0 的子树直接剪掉,总量 O(26 n) 以内)
void collect(ll c, ll node, ll l, ll r) {
    if (tree[c][node].sum == 0) return;
    if (l == r) {
        res[l] = (char)('a' + c);
        return;
    }
    push_down(c, node, l, r);
    ll mid = (l + r) >> 1;
    collect(c, node << 1, l, mid);
    collect(c, node << 1 | 1, mid + 1, r);
}

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

    cin >> n >> m;
    cin >> (s + 1);

    // 26 个字母各建一棵线段树
    for (ll c = 0; c < 26; c++) build(c, 1, 1, n);

    ll cnt[26];  // cnt[c] = 当前区间里字母 c 的个数
    for (ll q = 0; q < m; q++) {
        ll l, r, x;
        cin >> l >> r >> x;  // 输入顺序:左端点、右端点、方向(1 升序 / 0 降序)

        for (ll c = 0; c < 26; c++) cnt[c] = query(c, 1, 1, n, l, r);

        // 先清空区间内出现过的字母,否则旧字母会残留在自己的树里
        for (ll c = 0; c < 26; c++)
            if (cnt[c] > 0) assign_range(c, 1, 1, n, l, r, 0);

        // 再按升序 / 降序把各字母的计数整段铺回去
        ll pos = l;
        if (x == 1) {
            for (ll c = 0; c < 26 && pos <= r; c++) {
                if (cnt[c] > 0) {
                    assign_range(c, 1, 1, n, pos, pos + cnt[c] - 1, 1);
                    pos += cnt[c];
                }
            }
        } else {
            for (ll c = 25; c >= 0 && pos <= r; c--) {
                if (cnt[c] > 0) {
                    assign_range(c, 1, 1, n, pos, pos + cnt[c] - 1, 1);
                    pos += cnt[c];
                }
            }
        }
    }

    for (ll c = 0; c < 26; c++) collect(c, 1, 1, n);
    res[n + 1] = '\0';
    cout << (res + 1) << '\n';
    return 0;
}

复杂度

  • 时间:O((n+26m)log⁡n)O\big((n + 26m)\log n\big)。 C++ 版把"26 次求和 + 26 次清零 + 26 次覆盖"折成常数 7878, 实测 n=m=105n = m = 10^5 的顶格点约 0.5 s(限时 3000 ms)。 Python 版每次操作用 O(log⁡n)O(\log n) 次二分定位边界,加上均摊 O(26)O(26) 次段的重建, 段的总新增量被 O(n+26m)O(n + 26m) 兜住,所以同样是均摊 O((n+26m)log⁡n)O\big((n + 26m)\log n\big); 常数比线段树小,但 m=105m = 10^5 时 Python 仍需数秒,属于本 skill 允许的 "Python 可以比 C++ 慢"的范围,算法没有降级。
  • 空间:C++ 版 O(26n)O(26n)(26 × 4n 个线段树节点, 每个节点只有 int sum 与 signed char lazy); Python 版 O(n+26m)O(n + 26m) 个段,顶格下实际段数远小于此(每次操作后区间内至多 26 段)。
  • 与 40% 档的关系:n,m⩽103n, m \leqslant 10^3 时两份代码都在 0.1 s 以内, 40% 的部分分不需要额外写法。

总结

  • 排序只需要计数。 一次区间排序的输出完全由"26 个字母各有多少个"决定, 把"排 r−l+1r-l+1 个字符"换成"数 26 个数字,再整段铺回",是本题全部优化的出发点。
  • 计数用区间求和,结果用区间赋值。 26 棵 0/1 线段树同时提供这两种操作; 赋值必须带懒标记,否则每次都要改 O(r−l+1)O(r-l+1) 个叶子。
  • 清零不能忘。 26 棵树彼此独立,覆盖新字母之前必须把区间里出现过的旧字母整段清掉, 否则会出现"同一个位置在两棵树里都是 1"的矛盾状态。
  • 换个表示就是换个常数。 把"26 棵树"换成"同字母连续段列表", 同一套计数思想就得到了一个不用懒标记、不用递归的写法; 它的正确性靠"每次操作最多新增 26 段、删除总量被新增总量兜住"这条均摊论证。
  • 先校输入格式再写代码。 本题散文里的 (x,l,r)(x, l, r) 与样例的 (l,r,x)(l, r, x) 矛盾, 只有样例是可信的:按样例顺序读入才可能拿到 abdcc。