先上题目题目描述小明准备了 n 个节目节目顺序固定不能改变。需要从中选出 m 个节目要求满足选出的节目保持原顺序第一个节目尽可能好看在第一个最优的前提下第二个节目尽可能好看依次类推得到字典序最大的长度为 m 的子序列。输入描述第一行两个整数 n, m第二行n 个整数表示每个节目的好看值数据范围1 ≤ n ≤ 10⁵0 ≤ 节目好看值 ≤ 10⁵1 ≤ m ≤ n输出描述输出一行 m 个整数表示选出的节目好看值保持原顺序、字典序最大问题分析本题要求从 n 个数中选出 m 个保持顺序不变字典序最大。字典序最大的意思是第一位尽可能大 → 第一位确定后第二位尽可能大 → 依次类推。这是一个贪心问题但直接暴力贪心会超时必须用线段树优化。核心贪心规则假设已经选了前 k 个数字最后一个位置是 pos下一个数字必须在 pos1 到 n−(m−k−1) 的区间内选必须选这个区间里值最大的数如果有多个最大值选最左边的那个因为 n 达到 1e5每次区间查询最大值必须用 O(log n) 的数据结构线段树是最优选择。为什么要用线段树每次查询区间最大值 → 线段树 O (log n)总共查询 m 次 → 总复杂度 O (m log n)完美处理 1e5 数据不超时暴力贪心复杂度 O (nm)1e10 次运算直接超时。代码演示C#include iostream #include vector #include algorithm using namespace std; const int MAXN 1e5 10; int tree[MAXN 2]; int a[MAXN]; int n, m; // 线段树维护区间最大值的下标 void push_up(int id) { int left tree[id 1]; int right tree[id 1 | 1]; if (a[left] a[right]) tree[id] left; else tree[id] right; } void build(int id, int l, int r) { if (l r) { tree[id] l; return; } int mid (l r) / 2; build(id 1, l, mid); build(id 1 | 1, mid 1, r); push_up(id); } // 查询区间 [L, R] 内最大值的下标 int query(int id, int l, int r, int L, int R) { if (L l r R) { return tree[id]; } int mid (l r) / 2; int res -1; if (L mid) { int tmp query(id 1, l, mid, L, R); if (res -1 || a[tmp] a[res]) res tmp; else if (a[tmp] a[res]) res min(res, tmp); } if (R mid) { int tmp query(id 1 | 1, mid 1, r, L, R); if (res -1 || a[tmp] a[res]) res tmp; else if (a[tmp] a[res]) res min(res, tmp); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; for (int i 1; i n; i) cin a[i]; build(1, 1, n); vectorint ans; int last 0; for (int i 1; i m; i) { int L last 1; int R n - (m - i); int pos query(1, 1, n, L, R); ans.push_back(a[pos]); last pos; } for (int x : ans) cout x ; cout endl; return 0; }pythonimport sys sys.setrecursionlimit(1 25) def main(): import sys input sys.stdin.read data input().split() idx 0 n int(data[idx]) idx 1 m int(data[idx]) idx 1 a list(map(int, data[idx:idx n])) idx n a [0] a # 转成 1-based # 线段树存区间最大值的【最左下标】 size 1 while size n: size 1 tree_val [-1] * (2 * size) tree_idx [0] * (2 * size) # 建树 for i in range(1, n 1): tree_val[size i - 1] a[i] tree_idx[size i - 1] i for i in range(size - 1, 0, -1): left i 1 right i 1 | 1 if tree_val[left] tree_val[right]: tree_val[i] tree_val[left] tree_idx[i] tree_idx[left] elif tree_val[right] tree_val[left]: tree_val[i] tree_val[right] tree_idx[i] tree_idx[right] else: # 相等选左边 tree_val[i] tree_val[left] tree_idx[i] min(tree_idx[left], tree_idx[right]) # 查询 [l, r] 最大值的最左下标 def query(l, r): res_val -1 res_pos -1 l size - 1 r size - 1 while l r: if l % 2 1: if tree_val[l] res_val: res_val tree_val[l] res_pos tree_idx[l] elif tree_val[l] res_val: if tree_idx[l] res_pos: res_pos tree_idx[l] l 1 if r % 2 0: if tree_val[r] res_val: res_val tree_val[r] res_pos tree_idx[r] elif tree_val[r] res_val: if tree_idx[r] res_pos: res_pos tree_idx[r] r - 1 l 1 r 1 return res_pos ans [] last 0 for i in range(1, m 1): L last 1 R n - (m - i) pos query(L, R) ans.append(str(a[pos])) last pos print( .join(ans))算法详解1. 贪心思路最关键要选出长度为 m 的字典序最大子序列第 1 个数必须在 1 ~ n−m1 里选最大第 2 个数必须在 上一个位置 1 ~ n−m2 里选最大第 k 个数必须在 上一个位置 1 ~ n−mk 里选最大保证每一步都选当前能选的最大数字且最左边就能得到字典序最大。2. 线段树作用线段树在这里只做一件事给定区间 [L, R]快速返回值最大、且最靠左的下标。建树O (n)单次查询O (log n)m 次查询O (m log n)3. 为什么必须选最左边如果区间里有多个相同的最大值必须选最左边的这样右边剩下的数字更多能保证后面继续选出更大的数字。4. 时间复杂度建树O (n)m 次查询O (m log n)总复杂度O (n m log n)1e5 数据轻松通过5. 为什么不用单调栈单调栈也能做但线段树写法更直观、更通用、比赛更容易写对。本题官方标解、蓝桥杯标准解法就是线段树。结语本题是线段树最经典、最常考的应用题代码模板可以直接套用在所有区间最大值、区间选点、字典序最大子序列问题中。