问题分析

我们需要确定一个长度为 $n$ 的DNA序列中不同核苷酸种类的数量 $k$，并给出每个位置的核苷酸编号。关键约束是只能使用 $q$ 次区间查询操作，每次查询可以知道区间 $[i,j]$ 内不同核苷酸的数量。

核心思路

1. 关键观察

• 从左到右处理序列，对于每个新位置 $i$，我们需要判断它是否属于之前出现过的某种核苷酸类型
• 如果位置 $i$ 属于已有类型，那么区间 $[1,i]$ 的不同核苷酸数量不会增加；否则会增加1
• 通过维护每种类型最右出现位置，可以高效地进行类型匹配

2. 算法框架

算法采用在线处理策略，逐个确定每个位置的核苷酸类型：

1. 初始化：第一个位置自动分配类型1
2. 对于每个后续位置 $i$：
   • 查询区间 $[1,i]$ 的类型数量
   • 如果数量 ≤ 当前已知类型数，说明 $i$ 属于已有类型
   • 否则创建新类型

3. 二分查找优化

当确定位置 $i$ 属于已有类型时，需要找到具体是哪个类型。这里使用二分查找+线段树的方法：

• 线段树：维护每种类型最右出现位置的计数
• 二分策略：在候选区间 $[l,r]$ 内，检查中点 $m$：
  • 如果 $[m+1,i]$ 的类型数 = 右半区间计数 + 1，说明匹配类型在左半区间
  • 否则在右半区间继续查找

4. 数据结构设计

• classes[i]：位置 $i$ 的核苷酸类型编号
• rightmost_position[c]：类型 $c$ 最右出现位置
• tree[]：线段树，维护各类型最右位置的分布情况

算法流程

1. 初始化第一个位置为类型1
2. 循环处理 $i = 2$ 到 $n$：
   • 查询 $[1,i]$ 的类型数
   • 如果类型数不增加，执行二分查找找到匹配类型
   • 更新该类型的最右位置和线段树
3. 输出结果：类型总数和每个位置的类型编号

复杂度分析

• 查询次数：每个位置最多 $O(\log n)$ 次查询，总查询 $O(n \log n)$
• 时间复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$

算法优势

1. 在线处理：不需要存储所有查询结果，节省空间
2. 二分优化：将类型匹配的线性搜索优化为对数级别
3. 理论保证：在给定查询限制内一定能找到正确解

总结

本题的解法体现了交互式问题中常见的"逐步构建+二分查找"策略。通过维护类型的最右出现位置和利用线段树进行高效区间查询，算法在严格的查询次数限制下成功完成了DNA序列的破译任务。这种结合数据结构优化二分查找的方法在解决类似"在线分类"问题时具有很好的通用性。