分析
有的题目中存在区间内的点/子区间只能用一次的性质,那么这个时候就可以利用并查集将已经用过的点”挂”到没有用过的点上,然后就可以实现已经用过区间的删除
①疯狂的馒头
这道题即利用并查集,本质要解决的问题是对一个已经确定被染颜色的区间,就不能再次被染色,那么就要将这个区间删除,本题采用的删除策略即将区间内所有点都”挂”到整个区间右端点的下一个点上,被挂的右端点可能也被挂到了其他点上,但是因为$find$时存在路径压缩,可以直接用$p[l]=l+1$
②修改数组
本题是要将已经用过的点从序列中删除,同时需要快速的知道这个被删除的点值向上最近的没有被删除的点是什么,同理我们可以采用①中相同的策略,将所有被删除的点合并到它的下一个点上,下一个点可能也被删除了,但是因为$find$时存在路径压缩,所以我们同样可以直接用$p[x]=x+1$