TLE 了

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define int long long

int n, m;
int a[N];

int fa[N];
int find(int x) { if (x == fa[x]) return x; return fa[x] = find(fa[x]); }

int t[N<<1];
#define lowbit(x) ((x) & -(x))
void update(int x, int d) { a[x] += d; for (int i=x; i<=n; i+=lowbit(i)) t[i] += d; }
int get(int x) { int ret = 0; for (int i=x; i; i-=lowbit(i)) ret += t[i]; return ret; }
int query(int l, int r) { return get(r) - get(l-1); }

signed main()
{
	signed Case = 1;
	while (scanf("%lld", &n) != EOF)
	{
		for (int i=1, k; i<=n; i++) (cin >> k), update(i, k);
		iota(fa+1, fa+1+n+1, 1);
		printf("Case #%d:\n", Case ++);
		cin >> m; while (m --)
		{
			int k, l, r;
			cin >> k >> l >> r;
			if (l > r) swap(l, r);
			if (k == 0)
			{
				for (int i=l; i<=r; )
				{
					update(i, (int)(sqrt(a[i])) - a[i]);
					if (a[i] <= 1) fa[i] = i + 1;
					if (fa[i] == i) i ++;
					else i = find(fa[i]);
				}
			}
			else printf("%lld\n", query(l, r));
		}
		printf("\n");
		memset(a, 0, sizeof(a));
		memset(t, 0, sizeof(t));
		memset(fa, 0, sizeof(fa));
	}
	return 0;
}

从 P4145 上帝造题的七分钟 2 / 花神游历各国 这题过来的，本来想要双倍经验，结果TLE

大体思路就是，对于区间开方操作，暴力遍历区间，因为1e12开6次方就是1，然后用 fa[i] 维护 a 数组中 i 位置下一个不是 1 的位置（当 a[i]$≠$1时fa[i]=i）

觉得没有问题，一开始是用 ios::sync_with_stdio(false)和cin、cout，后来改成printf和scanf，还是TLE，求助