解题思路
本题要求对每个询问区间 [l,r],找出最早一次实验后,使得区间内所有容器属于同一个试剂族群。若至实验结束仍未统一,则输出 −1,初始状态视为 0 时刻。
观察实验过程:每次实验选择一个相邻位置对 (p,p+1),若当前两者不在同一族群,则将它们所在的整个族群合并。这本质上是依时间顺序将位置 p 和 p+1 所在的连通块合并,合并时间即为实验编号 k。因此,我们可以用 Kruskal 重构树 建模这一过程:
- 初始化重构树:初始时每个位置 i(1≤i≤n)为独立的叶子节点,共 n 个节点。
- 处理实验:按顺序遍历 t 次实验,第 k 次实验选择位置 p:
- 利用并查集找到 p 与 p+1 当前所在连通块的代表节点 fp,fp+1。