核心代码(路径压缩):

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

例题:

A.上帝造题的七分钟 2 / 花神游历各国

因为$10^{12}$最多开根号$6$次就变为$1$了,所以我们可以忽略值为$1$的元素

那么我们可以用线段树单点修改,这里提供并查集的实现方法

若$fa[i] = $i,则说明该值不等于$1$,否则该值等于后面第一个不等于$1$的点的位置(需要开根)

B.封印序列

将每次删除一个数倒过来转化为每次加入一个数, 将区间和作为值维护在祖宗节点上(区间右端点)

每次加入一个数, 判断左右是否有序列, 若有则合并

C.疯狂的馒头

逆思维: 每次将一个区间染色, 并删除这个区间

$p[x]$记录x右边第一个没有染色区间的左端点

$1.$若染一个点: $p[x]$ $=$ $find(x + 1)$

$2.$染一个区间: 将$find(l)$ ~ $r$中的点全部染色, 直至左端点大于右端点, 并不断更新$p[x]$, 用$x = find(x)$转移