题目大意

有 $N$ 个活动，第 $i$ 个活动在 $[L_i+0.1, R_i-0.1]$ 时间段举行。要选择恰好 $K$ 个不冲突的活动（一个活动结束后才能参加下一个），且选择的编号序列字典序最小。如果无法选择 $K$ 个活动，输出 -1。

解题思路

核心思想

贪心 + 倍增预处理 + 集合维护

1. 贪心选择：按编号从小到大尝试选择每个活动，保证字典序最小
2. 可行性判断：用倍增预处理快速计算从某个活动开始最多能选多少个活动
3. 冲突检测：用平衡树维护已选活动，检查时间冲突

关键算法

1. 倍增预处理

• nxt[i][j] 表示从活动 $i$ 开始，跳 $2^j$ 步后到达的活动
• 预处理出每个活动能参加的下一个最早结束的活动

2. 贪心策略

对于每个活动 $i$：

• 检查是否与已选活动冲突
• 计算如果选择该活动，最终能否选出 $K$ 个活动
• 如果可行就选择，否则跳过

算法流程

1. 预处理阶段：

   • 扫描线处理，构建 nxt 数组
   • 倍增预处理，快速计算最多可选活动数

2. 可行性检查：

   • 计算最多能选的活动总数 tot
   • 如果 tot < k，直接输出 -1

3. 贪心选择：

   • 按编号从小到大遍历活动
   • 对于每个活动，检查是否与已选活动冲突
   • 用倍增快速计算选择该活动后是否还能选出 $K$ 个活动
   • 如果可行就选择并输出

复杂度分析

• 时间复杂度：$O(N \log N)$

  • 排序：$O(N \log N)$
  • 倍增预处理：$O(N \log N)$
  • 贪心选择：$O(N \log N)$

• 空间复杂度：$O(N \log N)$

总结

本题是一个经典的区间调度+字典序最小化问题，其核心难点在于如何在保证选出恰好 $K$ 个不冲突活动的前提下，得到字典序最小的选择方案。解题的关键在于：

1. 预处理优化：通过倍增技术预处理出每个活动后续的最优选择链，使得能够快速计算从任意活动开始最多能选择多少个活动。

2. 贪心策略：按编号从小到大尝试选择活动，对于每个候选活动，需要：

   • 检查与已选活动的时间冲突
   • 利用预处理信息快速判断选择该活动后是否还能凑够 $K$ 个活动

3. 高效维护：使用平衡树（set）来维护已选活动，便于快速查找相邻活动进行冲突检测。