花神游历各国（树状数组，并查集优化修改区间）

花神游历各国（树状数组，并查集优化修改区间）

传送门
题意：给你一个含有n个字符的序列，进行两种 *** 作，每行三个整数 x,l,r，当 x=1 时询问游历国家 l到 r 的区间总和，当x=2时，区间的每个数字都变为该数字开方后的数值。

分析：区间修改开方数值，如果暴力修改的话会超时。
优化：有一些区间多次开方就是变为1，如果是1的下次就跳过了，所以用并查集，如果发现<=1(还有初值可能为0的情况，其他开方的数都大于1），则父节点标为该点的值+1，下次遍历就跳过这个到下下个数了。
ac代码：

#include
#include
#include
#include
using namespace std;
typedef long long ll;
int INF=0x3f3f3f3f;
int mod=10007,n,q;
ll bit[100010],ar[100010];
int fa[100010];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,ll z)
{
    for(int i=x;i<=n;i+=lowbit(i))
        bit[i]+=z;
}
ll query(int x)
{
    ll sum=0;
    while(x)sum+=bit[x],x-=lowbit(x);
    return sum;
}
int Fi(int x)
{
	if(fa[x]==x) 
	return x;
	else return fa[x]=Fi(fa[x]);
}
int main()
{
    int op,l,r;
    while(~scanf("%d",&n))
    {
        memset(bit,0,sizeof(bit));
        for(int i=1; i<=n; ++i)
        {
            scanf("%lld",&ar[i]);
            add(i,ar[i]);
        }
        for(int i=1;i<=n;i++)
            fa[i]=i;
        fa[n+1]=n+1;
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d%d",&op,&l,&r);
            if(op==2)
            {
                for(int j=l;j<=r;)
                {
                    ll tmp=(ll)sqrt(ar[j]);
                    add(j,tmp-ar[j]);
                    ar[j]=tmp;
                    fa[j]=j;
                    if(tmp<=1)//不用重复开方的
                        fa[j]=j+1;
                    j=(	Fi(j)==j?j+1:fa[j]	);//找下次需要更新的位置在哪里 
                }
            }
            else
            printf("%lldn", query(r)-query(l-1));
        }
    }
    return 0;
}