思路：
一眼思路：线段树区间修改，区间查询。
发现bug：区间的sqrt无法实现，所以还是相当于对区间的每一个点进行单点修改，所以一定会超时。
后来经过仔细观察：
可以发现，由于所有的邪恶战舰的耐力值之和小于263 (You can assume that the sum of all endurance value is less than 2 63. )
所以每艘战舰的耐力值最多被开平方6次，不会超过7次。所以从这里入手开始答题。
每个数被开平方后，最后的结果会变成1。所以当区间和等于区间长度时，不再进行更新。
加上这个剪枝后，就可以AC了。
错误：今天总是遇见一些奇奇怪怪的错误ヽ(￣ω￣(￣ω￣〃)ゝ 竟然会Presentation Error。在两个数据的答案之间要加上一个换行，样例连点说明都木有。
#include#include #include #include #include #define MAXN 100010using namespace std;int n,m,tot;struct nond{ long long sum; int l,r,len,flag;}tree[MAXN*4];void up(int now){ tree[now].sum=tree[now*2].sum+tree[now*2+1].sum;}void build(int now,int l,int r){ tree[now].l=l;tree[now].r=r; tree[now].len=tree[now].r-tree[now].l+1; if(tree[now].l==tree[now].r){ scanf("%lld",&tree[now].sum); return ; } int mid=(tree[now].l+tree[now].r)/2; build(now*2,l,mid); build(now*2+1,mid+1,r); up(now);}void change(int now,int l,int r){ if(tree[now].sum==tree[now].len) return ; if(tree[now].l==tree[now].r){ tree[now].sum=(long long)sqrt(tree[now].sum); return ; } int mid=(tree[now].l+tree[now].r)/2; if(r<=mid) change(now*2,l,r); else if(l>mid) change(now*2+1,l,r); else{ change(now*2,l,mid);change(now*2+1,mid+1,r); } up(now);}long long query(int now,int l,int r){ if(tree[now].l==l&&tree[now].r==r) return tree[now].sum; int mid=(tree[now].l+tree[now].r)/2; if(r<=mid) return query(now*2,l,r); else if(l>mid) return query(now*2+1,l,r); else return query(now*2,l,mid)+query(now*2+1,mid+1,r);}int main(){ while(scanf("%d",&n)!=EOF){ ++tot;printf("Case #%d:\n",tot); build(1,1,n); scanf("%d",&m); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); if(y>z) swap(y,z); if(x==0) change(1,y,z); else printf("%lld\n",query(1,y,z)); } cout<