给定彩带的长度 N 和每一格的颜色(0=白，1=红)，K次的着色(保证会在白色格子涂红)， 输出的两个数字分别为每次着色後最长和最短的红色区间长度总和。 这题会用到 DSU 连通的概念，维护每次着色後最长的红色区间长度问题不大。 但问题点在於维护最短区间长度。 因为着色的关系，导致最多2个区间合并，代表 RootID 的长度会被改变。 又因为格子个数最多会有 1e5 个，暴力法理论上应该不可行。 我只想到 Mapping HEAP 这个资料结构(不确定有没有这种东西...)。 基础的 HEAP 资料结构加上一个映射阵列( mapp[RootID]=这个 RootID在HEAP的位置 ) 这个 HEAP 只维护 每个 Group 的代表ID 并且依照长度维护(越小越上层)。 保证某个 RootID 长度被改变时是 ㏒N (HeapDown)， 或是因为区间合并导致需要删除某个存在 HEAP 内的 RootID 时是 ㏒N (HeapUp+Down)。 不过考虑到这题属 APCS，应该存在某种合理的资料结构应付上述需求? 至少不是要当场写这种 Mapping HEAP吧... 最後附上程式码：https://www.codepile.net/pile/NG2lD4rl ※ 编辑: fatcat8127 (61.222.86.91 台湾), 11/08/2020 01:57:38 ※ 编辑: fatcat8127 (101.12.22.166 台湾), 11/08/2020 03:36:07 你说的我有想过，不过不把因为合并的点删除时会导致整个 HEAP 根据长度排序会出问题 如果是要根据合并後的 Group ID 长度为统一时，代表需要同步调整个 HEAP 当中 属於这个 Group 的其他点确保 HEAP 的架构正确。 ※ 编辑: fatcat8127 (61.222.86.91 台湾), 11/08/2020 22:59:37 後来想到可以用 multiset(存在多个长度相同的Group)+struct(定义小於=根据长度排序) muiltiset.find() 可以找到指定的 struct，可以直接 erase， 但是找到的 struct 是 read-only，所以更新某个已经存在的 Group 长度时， 需要 erase older version + insert new version(after updating)。 这边附上实作的程式：https://www.codepile.net/pile/gaWjg6vb ※ 编辑: fatcat8127 (61.222.86.91 台湾), 11/09/2020 12:30:51