本蒟蒻用的并查集+树状数组，但是它T了，连O2也卡不过去

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,t[100001],a[100001],fa[100001],q,ca=1;
inline ll lowbit(ll x)
{
	return x&(-x);
}
inline ll find(ll x)
{
	if(x==fa[x])
	return x;
	else
	return x=fa[x];	
}
inline void update(ll x,ll k)
{
	while(x<=n)
	{
		t[x]+=k;
		x+=lowbit(x);
	}
}
inline ll query(ll x)
{
	ll res=0;
	while(x)
	{
		res+=t[x];
		x-=lowbit(x);
	}
	return res;
}
int main()
{
	while(cin>>n)
	{
		memset(t,0,sizeof(t));
		for(int i=1;i<=n;i++)
		fa[i]=i;
		fa[n+1]=n+1;
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			update(i,a[i]);
		}
		scanf("%lld",&q);
		printf("Case #%d:\n",ca++);
		for(int i=1;i<=q;i++)
		{
			ll op,x,y;
			scanf("%lld%lld%lld",&op,&x,&y);
			if(x>y)
			swap(x,y);
			if(op==1)
			printf("%lld\n",query(y)-query(x-1));
			if(op==0)
			while(x<=y)
			{
				ll t=sqrt(a[x]);
				update(x,t-a[x]);
				a[x]=t;
				if(a[x]<=1)
				fa[x]=x+1;
				else
				fa[x]=x;
				if(fa[x]==x)
				x=x+1;
				if(fa[x]!=x)
				x=find(x);
			}
		}
		puts("");
	}
	return 0;
}