***又是超时的问题，当一个区间全是1时，再去开方和不开方是一样的，所以在这一步不需要再往底层递归了***
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <stack> #include <queue> #include <cmath> using namespace std; typedef long long LL; #define oo 0x3f3f3f3f #define N 201000 struct node { int l, r; int len() { return r-l+1; } LL s; } tree[N*4]; LL A[N];//数据较大，元素用long long void build(int l, int r, int rt) { tree[rt].l=l; tree[rt].r=r; if(l==r) { tree[rt].s=A[l]; return ; } int mid=(l+r)/2; build(l, mid, rt*2); build(mid+1, r, rt*2+1); tree[rt].s=tree[rt*2].s+tree[rt*2+1].s; } void update(int l, int r, int rt) { if(tree[rt].len()==tree[rt].s)//当一个区间全是1时 return ; if(tree[rt].r<l || tree[rt].l>r) return ; if(tree[rt].l>=l && tree[rt].r<=r && tree[rt].l==tree[rt].r) { tree[rt].s=(LL)sqrt(tree[rt].s); return ; } int mid=(tree[rt].l+tree[rt].r)/2; if(r<=mid) update(l, r, rt*2); else if(l>mid) update(l, r, rt*2+1); else { update(l, mid, rt*2); update(mid+1, r, rt*2+1); } tree[rt].s=tree[rt*2].s+tree[rt*2+1].s; } LL query(int l, int r, int rt) { if(tree[rt].l==l && tree[rt].r==r) return tree[rt].s; int mid=(tree[rt].l+tree[rt].r)/2; if(r<=mid) return query(l, r, rt*2); else if(l>mid) return query(l, r, rt*2+1); else { LL x=query(l, mid, rt*2); LL y=query(mid+1, r, rt*2+1); return x+y; } } int main() { int n, m, op, a, b, cas=1; while(~scanf("%d", &n)) { for(int i=1; i<=n; i++) scanf("%I64d", &A[i]); scanf("%d", &m); build(1, n, 1); printf("Case #%d: ", cas++); while(m--) { scanf("%d%d%d", &op, &a, &b); if(a>b) swap(a, b);//记住a可能大于b,就这个错误，我交了n次，都是RE if(op==0) update(a, b, 1); else printf("%I64d ", query(a, b, 1)); } printf(" "); } return 0; }