题解：「ROI 2023 Day2 T2」Конференция（基于提供代码）

核心思路总览

本题通过 贪心求最大相容集合 + 分区域筛选 构造答案，核心逻辑是：先找到原活动的最大相容集合（大小 ( m )），再以集合中间位置为界，分左右两个区域筛选活动，最终保留 ( \frac{n}{2} ) 个活动，确保新集合的最大相容集合大小为 ( \frac{m}{2} )。整体复杂度 ( O(n\log n) )（排序主导），适配 ( 10^5 ) 规模数据。

关键步骤拆解

1. 求原问题的最大相容集合（贪心经典算法）

最大相容集合即“最大不相交区间集”，采用贪心策略求解：

• 排序：将所有活动按 结束时间 ( r_i ) 升序排序（贪心选择结束最早的活动，为后续活动预留更多空间）。
• 筛选：初始化前一个活动结束时间 pre = 0，遍历排序后的活动，若当前活动的开始时间 ( l_i > pre )，则加入最大相容集合，更新 pre = r_i。
• 最终得到最大相容集合的索引数组 as（存储排序后活动的下标），其长度 as[0] = m（原最大相容集合大小）。

2. 确定分界点与筛选区域

• 取最大相容集合的中间位置 ip = m / 2，对应的活动为 id = as[ip]（排序后下标），该活动的结束时间 p[id].r 作为分界点。
• 整个活动集合被分为两个区域：
  • 左区域：活动开始时间 ( l_i \leq p[id].r )（与分界活动有重叠或在其之前结束）。
  • 右区域：活动开始时间 ( l_i > p[id].r )（与分界活动无重叠，在其之后开始）。
• 统计左区域的活动总数 cnt，以此决定从哪个区域优先筛选活动。

3. 筛选目标活动（保留 ( \frac{n}{2} ) 个）

核心原则：确保左区域的最大相容集合大小 ≤ ( \frac{m}{2} )，右区域的最大相容集合大小 ≤ ( \frac{m}{2} )，且总保留数为 ( \frac{n}{2} )。

情况1：左区域活动数 ≥ ( \frac{n}{2} )

• 先保留最大相容集合的前 ( \frac{m}{2} ) 个活动（as[1] 到 as[ip]），这些活动均在左区域，且彼此不相交，构成大小为 ( \frac{m}{2} ) 的相容集合。
• 剩余需要补充的活动从左区域未选中的活动中任选（左区域活动充足），直到凑够 ( \frac{n}{2} ) 个。
• 此时左区域最大相容集合大小为 ( \frac{m}{2} )，右区域无选中活动，整体最大相容集合大小为 ( \frac{m}{2} )。

情况2：左区域活动数 < ( \frac{n}{2} )

• 先保留最大相容集合的后 ( \frac{m}{2} ) 个活动（as[ip+1] 到 as[m]），这些活动均在右区域，且彼此不相交，构成大小为 ( \frac{m}{2} ) 的相容集合。
• 剩余需要补充的活动从右区域未选中的活动中任选，直到凑够 ( \frac{n}{2} ) 个。
• 此时右区域最大相容集合大小为 ( \frac{m}{2} )，左区域无选中活动，整体最大相容集合大小为 ( \frac{m}{2} )。

4. 输出结果

• 用 flg 数组标记选中的活动（排序后的下标），最终输出这些活动的原始编号 p[i].id。

代码解析

1. 输入处理与排序

• 读取测试组数 ( T )，每组数据读取 ( n ) 和 ( n ) 个活动的 ( l_i, r_i ) 及原始编号 id。
• 按活动结束时间 ( r_i ) 升序排序，存储在数组 p 中。

2. 贪心求最大相容集合

• 遍历排序后的活动，筛选出最大不相交区间集，存储在 as 数组中（as[0] 为集合大小 ( m )）。

3. 分界点与区域统计

• 计算 ip = m / 2 和分界活动 id = as[ip]，统计左区域活动数 cnt。

4. 活动筛选与标记

• 根据 cnt 与 ( \frac{n}{2} ) 的大小关系，选择左/右区域优先筛选，用 flg 标记选中的活动。

5. 结果输出

• 遍历 flg 数组，输出所有被标记活动的原始编号。

关键验证（结合样例）

以第一组样例为例：

• 原活动排序后，最大相容集合 as 包含 4 个活动（( m=4 )），ip=2，分界活动为 as[2]（排序后下标），其 r_i 为分界点。
• 左区域活动数 cnt ≥ 4（( \frac{n}{2}=4 )），先保留 as[1] 和 as[2]（前 2 个，即 ( \frac{m}{2}=2 )），再从左区域补充 2 个活动，最终选中 4 个活动，其最大相容集合大小为 2，符合要求。

复杂度分析

• 时间复杂度：( O(n\log n) )，排序占主导，后续遍历均为 ( O(n) )。
• 空间复杂度：( O(n) )，存储活动数组、标记数组和最大相容集合数组。

关键结论

本题的核心是利用贪心算法找到最大相容集合，再通过“中间分界”拆分集合，确保筛选后的活动满足“最大相容集合大小减半”的要求。构造思路巧妙，无需复杂数据结构，仅通过排序和贪心即可高效求解。

要不要我帮你补充边界情况（如 ( m=2 )、所有活动不相交）的验证，或优化代码的细节（如减少数组开辟）？