把串切成同字母的连续段,每次排序先二分定位区间内的段、统计 26 个字母的计数,再按升/降序整段铺回,段数均摊 O(n+26m)。
OJ: roj
题目 ID: 1751
难度:提高+/省选-
标签:数据结构线段树区间赋值python
创建: 2026-10-07 21:10
更新: 2026-10-07 21:10
形式化题目
给定长度为
:把子串 升序排序; :把子串 降序排序。
排序会覆盖原来的字符,后续操作看到的是上一步的结果。求全部操作结束后的完整字符串。
输入顺序的坑。 题面散文写"接下来
行每行三个整数 ", 但【输入样例】两行是 1 3 1和3 5 0, 只有按解释才能得到样例输出: 升序把 cab排成abc,降序把 ccd排成dcc, 全串变成abdcc。若按解释,第一行就要求 ,非法。 因此本题实际输入顺序是 ,正文以下的推导都按这个顺序。
本题与 Codeforces 558E “A Simple Task” 同源:题面、样例、数据范围(
样例的逐步过程:
| 步骤 | 串 | 说明 |
|---|---|---|
| 初始 | c a b c d |
|
a b c c d |
cab 升序 → abc |
|
a b d c c |
ccd 降序 → dcc |
正解
思路
先看朴素做法的瓶颈。 最直接的做法是每次把区间内的字符取出来排序再写回:
S[l:r+1] = sorted(S[l:r+1]),单次
关键观察:排序的输入只需要"计数"。 一次排序
于是真正需要维护的只有两件事:区间内 26 个字母的计数,和区间被整段覆盖成某个字母。 这两个需求正是"区间求和 + 区间赋值",线段树(或树状数组 + 并查集)能办。
两种实现路线。
| 路线 | 维护什么 | 单次操作代价 |
|---|---|---|
计数型(main.cpp) |
26 棵线段树,第 |
|
段型 / ODT(main.py) |
直接维护"同字母的连续段"列表 | 均摊 |
计数型(main.cpp)。 每个字母
- 对
求出 cnt_c = $ 第 $c 棵树的区间和; - 把
中出现过的字母整段清零( 的那些)。 这一步不能省:26 棵树彼此独立,"给 a 树赋值"不会顺手清掉 b 树里的旧标记, 残留字符会和新的区间划分冲突; - 从
出发, 时 从 0 枚举到 25, 时从 25 枚举到 0, 对每个 的字母把 整段赋值成 1, 右移。
区间赋值需要懒标记:整段被覆盖成常量后,该节点的和可以直接算出,
直到下一次需要下探才把标记推给孩子。这样单次操作
段型 / ODT(main.py)。 换个更贴合题意的表示:把整串切成若干同字母的连续段,
只存每段的起点和字母。例如 cabcd 是 5 段,而样例第一次排序后 abccd 只有 4 段。
一次排序
- 先按
与 把边界切开(二分找到落点,必要时把一段拆成两段), 这样区间 恰好由若干完整段拼成; - 累加这些段的长度得到
; - 删掉这些段,按
的顺序用 重建最多 26 个新段; 首尾与区间外同字母的邻段合并,避免段数虚增。
段数不会爆:初始最多
为什么两个版本都写? 本题的 data/ 由 data.py 生成、标程是 26 棵线段树的版本,
顶格数据 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 定位段边界;只需标准库):
#!/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 棵线段树,区间求和 + 区间赋值):
/**
* 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;
}复杂度
- 时间:
。 C++ 版把"26 次求和 + 26 次清零 + 26 次覆盖"折成常数 , 实测 的顶格点约 0.5 s(限时 3000 ms)。 Python 版每次操作用 次二分定位边界,加上均摊 次段的重建, 段的总新增量被 兜住,所以同样是均摊 ; 常数比线段树小,但 时 Python 仍需数秒,属于本 skill 允许的 "Python 可以比 C++ 慢"的范围,算法没有降级。 - 空间:C++ 版
( 26 × 4n个线段树节点, 每个节点只有int sum与signed char lazy); Python 版个段,顶格下实际段数远小于此(每次操作后区间内至多 26 段)。 - 与 40% 档的关系:
时两份代码都在 0.1 s 以内, 40% 的部分分不需要额外写法。
总结
- 排序只需要计数。 一次区间排序的输出完全由"26 个字母各有多少个"决定,
把"排
个字符"换成"数 26 个数字,再整段铺回",是本题全部优化的出发点。 - 计数用区间求和,结果用区间赋值。 26 棵 0/1 线段树同时提供这两种操作;
赋值必须带懒标记,否则每次都要改
个叶子。 - 清零不能忘。 26 棵树彼此独立,覆盖新字母之前必须把区间里出现过的旧字母整段清掉, 否则会出现"同一个位置在两棵树里都是 1"的矛盾状态。
- 换个表示就是换个常数。 把"26 棵树"换成"同字母连续段列表", 同一套计数思想就得到了一个不用懒标记、不用递归的写法; 它的正确性靠"每次操作最多新增 26 段、删除总量被新增总量兜住"这条均摊论证。
- 先校输入格式再写代码。 本题散文里的
与样例的 矛盾, 只有样例是可信的:按样例顺序读入才可能拿到 abdcc。