$\quad $ 在解决区间问题时，如果直接修改或者线段树不好维护且总共的有效修改很小时，我们就可以考虑使用并查集来解决问题。
$\quad $ 问题中的各元素需要满足一定的条件，我们在遍历的时候，如果当前元素修改完之后仍然满足条件，那么我们就可以直接跳到后面的位置后面第一个满足条件的位置，反之，则将当前位置连到后面位置上即可。
一道简单的线段树问题
$\quad $ 观察数据范围可知（这里没有展示），每个数在被开方 \(6\) 次之后就会变成 \(1\) ，在变为 \(1\) 后对其开方无意义，所以我们可以使用并查集维护某位数字之后（包括这位数字）第一个需要开方的数字的位置，这样就可以很快地跳到需要更改的位置，总的更改次数不超过 \(6n\) ，即可通过此题。
点击查看代码
#define yhl 0
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+100;
int fa[N],a[N],n,m,l,r,c[N],k;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int get_sum(int x){
if(!x)return yhl;
int ans=0;
while(x){ans+=c[x];x-=(x&-x);}
return ans;
}
void add(int x,int y){
if(!x)return;
while(x<=n){c[x]+=y;x+=(x&-x);}
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
fa[i]=i;
scanf("%lld",&a[i]);
add(i,a[i]);
}
fa[n+1]=n+1;
scanf("%lld",&m);
while(m--){
scanf("%lld%lld%lld",&k,&l,&r);
if(k)printf("%lld\n",get_sum(r)-get_sum(l-1));
else{
for(int i=find(l);i<=r;i=find(i)){
int op=(int)sqrt(a[i])-a[i];
add(i,op);
a[i]=sqrt(a[i]);
if(a[i]==1)fa[i]=i+1;
else i++;
}
}
}
return yhl;
}
$\quad $ 例题：白雪皑皑
标签：return,int,查集,fa,ans,跳跃,quad From： https://www.cnblogs.com/0shadow0/p/18314710