先上题目
题目描述
小明准备了 n 个节目，节目顺序固定不能改变。需要从中选出 m 个节目，要求满足：
- 选出的节目保持原顺序；
- 第一个节目尽可能好看；
- 在第一个最优的前提下，第二个节目尽可能好看；
- 依次类推，得到字典序最大的长度为 m 的子序列。
输入描述
第一行：两个整数 n, m第二行：n 个整数，表示每个节目的好看值
数据范围1 ≤ n ≤ 10⁵0 ≤ 节目好看值 ≤ 10⁵1 ≤ m ≤ n
输出描述
输出一行 m 个整数，表示选出的节目好看值（保持原顺序、字典序最大）
问题分析
本题要求从 n 个数中选出 m 个，保持顺序不变，字典序最大。字典序最大的意思是：第一位尽可能大 → 第一位确定后第二位尽可能大 → 依次类推。
这是一个贪心问题，但直接暴力贪心会超时，必须用线段树优化。
核心贪心规则
假设已经选了前 k 个数字，最后一个位置是 pos：
- 下一个数字必须在 pos+1 到 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); vector<int> 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; }python
import 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−m+1 里选最大
- 第 2 个数：必须在 上一个位置 + 1 ~ n−m+2 里选最大
- 第 k 个数：必须在 上一个位置 + 1 ~ n−m+k 里选最大
保证每一步都选当前能选的最大数字，且最左边，就能得到字典序最大。
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. 为什么不用单调栈？
单调栈也能做，但线段树写法更直观、更通用、比赛更容易写对。本题官方标解、蓝桥杯标准解法就是线段树。
结语
本题是线段树最经典、最常考的应用题，代码模板可以直接套用在所有区间最大值、区间选点、字典序最大子序列问题中。
