对区间中的每一个数进行开平方操作，其实还是对单点进行操作。
所以需要进行一些优化，不然会超时：在updata中，当节点区间 已经被 查询区间包含，并且节点区间的val等于节点区间的长度（即节点中的值全为1），return。
因为是开方操作，即使很大的数也开不了几次方就到1了，所以这样优化可以节省大量时间。
另外：
输入的X, Y 不保证 X<Y。每一组样例后面要多一空行。
ac代码：
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <vector> using namespace std; typedef long long ll; const int maxn = 1e5 + 5; struct node { ll l, r, val; }tree[maxn<<2]; ll arr[maxn]; void pushup(ll k) { tree[k].val = tree[k << 1].val + tree[k << 1 | 1].val; return; } void build(ll l, ll r, ll k) { tree[k].l = l; tree[k].r = r; if (l == r) { tree[k].val = arr[l]; return; } ll mid = (l + r) >> 1; build(l, mid, k << 1); build(mid + 1, r, k << 1 | 1); pushup(k); return; } void updata(ll l, ll r, ll k) { if (tree[k].l == tree[k].r) { tree[k].val = sqrt(tree[k].val); return; } if (l <= tree[k].l && r >= tree[k].r && tree[k].val == tree[k].r - tree[k].l + 1) return; ll mid = (tree[k].l + tree[k].r) >> 1; if(l <= mid) updata(l, r, k << 1); if(r > mid) updata(l, r, k << 1 | 1); pushup(k); return; } ll query(ll l, ll r, ll k) { if (l <= tree[k].l && r >= tree[k].r) { return tree[k].val; } ll mid = (tree[k].l + tree[k].r) >> 1; ll res = 0; if (l <= mid) res += query(l, r, k << 1); if (r > mid) res += query(l, r, k << 1 | 1); return res; } int main() { int n, m, Case = 1; while (~scanf("%d", &n)) { printf("Case #%d: ", Case++); memset(tree, 0, sizeof(tree)); for (int i = 1; i <= n; i++) scanf("%lld", &arr[i]); build(1, n, 1); scanf("%d", &m); for (int i = 0; i < m; i++) { ll c, l, r; scanf("%lld %lld %lld", &c, &l, &r); if (l > r) swap(l, r); if (c == 0) updata(l, r, 1); if (c == 1) printf("%lld ", query(l, r, 1)); } printf(" "); } return 0; }