给你 n 个数，依次标号为 1, 2, … ， n。
有两种操作，一种是对区间 x, y 内的每个数进行开方，开方后的数取整数；另一种是问区间 x, y 内数的和。

虽然说每个数都可以很大，但是开方开到一定次数后就变成 1，再对 1 开方也就没必要了。因此用线段树，增加一个值来看所操作区间下的数是否都为 1，若都是 1 也就没必要再对其进行操作了。

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 100005;
struct edge {
  i64 sum;
  bool flag;
} e[N << 2];
void build(int l, int r, int rt)
{
  if (l == r) {
    scanf("%lld", &e[rt].sum);
    e[rt].flag = (e[rt].sum == 1) ? 1 : 0;
  } else {
    int m = l + r >> 1;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    e[rt].sum = e[rt << 1].sum + e[rt << 1 | 1].sum;
    e[rt].flag = e[rt << 1].flag & e[rt << 1 | 1].flag;
  }
}
void update(int ll, int rr, int l, int r, int rt)
{
  if (e[rt].flag) {
    return;
  }
  if (l == r) {
    e[rt].sum = (int) sqrt(1.0 * e[rt].sum);
    e[rt].flag = (e[rt].sum == 1) ? 1 : 0;
    return;
  }
  int m = l + r >> 1;
  if (ll <= m)
    update(ll, rr, l, m, rt << 1);
  if (rr > m)
    update(ll, rr, m + 1, r, rt << 1 | 1);
  e[rt].sum = e[rt << 1].sum + e[rt << 1 | 1].sum;
  e[rt].flag = e[rt << 1].flag & e[rt << 1 | 1].flag;
}
i64 query(int ll, int rr, int l, int r, int rt)
{
  if (ll <= l && r <= rr) {
    return e[rt].sum;
  }
  i64 res = 0;
  int m = l + r >> 1;
  if (ll <= m)
    res += query(ll, rr, l, m, rt << 1);
  if (rr > m)
    res += query(ll, rr, m + 1, r, rt << 1 | 1);
  return res;
}
int main()
{
  int n, cas = 1;
  while (~scanf("%d", &n)) {
    printf("Case #%d:\n", cas++);
    build(1, n, 1);
    int m;
    scanf("%d", &m);
    while (m--) {
      int a, x, y;
      scanf("%d %d %d", &a, &x, &y);
      if (x > y)
        swap(x, y);
      if (a) {
        printf("%lld\n", query(x, y, 1, n, 1));
      } else {
        update(x, y, 1, n, 1);
      }
    }
    puts("");
  }
  return 0;
}