题目 https://judge.tcirc.tw/ShowProblem?problemid=d101
给定彩带的长度 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