题意：
给n个数字，修改操作为：区间[a,b]内的每个值改为他的平方根。询问操作：给出区间[c,d]内的总和。
题解：
线段树：区间set，区间sum。
这道题的set不是简单的每个节点都加加减减的问题了，而是每个节点开根号，所有就不能用懒惰标记进行优化了，但是反过来想，由于每个节点都是开方，所以每个节点的数降低的都是非常快的，6-7次就降到1了，降到1，以后就没必要进行再开方了，所以本题的优化不在于pushdown，而在于判断区间内是否全部为1了，如果全为1，则可以不必再更新！
题目给的区间边界需要判断下是否合理，不合理的调换下！这个还是认真读题的了，题目说得是
between the X-th and Y-th battleship
，
并没有说x比y小。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<cmath>
#include<cctype>
#define INF 0x3f3f3f3fusing namespace std;#define lson 2*i,l,m
#define rson 2*i+1,m+1,rconst int maxn=100000+10;
long long sum[maxn<<2];void pushup(int i)
{sum[i]=sum[2*i]+sum[2*i+1];
}void build(int i, int l, int r)
{if(l==r){scanf("%I64d",&sum[i]);return;}int m=(l+r)/2;build(lson);build(rson);pushup(i);
}void update(int ql, int qr, int i, int l, int r)
{if(l==r){sum[i]=sqrt(1.0*sum[i]);return;}if(ql<=l&&qr>=r&&sum[i]==r-l+1)return;int m=(l+r)/2;if(ql<=m)update(ql,qr,lson);if(qr>m)update(ql,qr,rson);pushup(i);
}long long query(int ql,int qr,int i,int l,int r)
{if(ql<=l&&qr>=r)return sum[i];int m=(l+r)/2;long long res=0;if(ql<=m)res+=query(ql,qr,lson);if(qr>m)res+=query(ql,qr,rson);return res;
}int main()
{int kase=1;int n,m;while(cin>>n){printf("Case #%d:\n",kase++);build(1,1,n);cin>>m;while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(b>c)swap(b,c);if(a)printf("%lld\n",query(b,c,1,1,n));else update(b,c,1,1,n);}puts("");}
}