http://acm.hdu.edu.cn/showproblem.php?pid=4027
题意：给一个数组序列， 数组长度为100000，现在有两种操作， 一种操作是将某一个固定区间所有数开方（向下取整），另一种操作是询问某个区间的所有数字之和。
题解：线段树：单点更新，区间求和。注意一个可以优化的地方：在query和update操作中，如果segTree[rt]==r-l+1，说明该区间内所有数都为1，开方也是1,则不必递归下去了。
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include <string.h>
using namespace std;
#define maxn 100010
typedef long long LL;
LL segTree[maxn<<2];
void build(int l,int r,int rt)
{
if(l==r)
{
scanf("%lld",&segTree[rt]);
return;
}
int mid=l+((r-l)>>1);
build(l,mid,rt<<1);
build(mid+1,r,(rt<<1)|1);
segTree[rt]=segTree[rt<<1]+segTree[(rt<<1)|1];
}
LL query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R) return segTree[rt];
if(L<=l&&r<=R&&segTree[rt]==r-l+1) return r-l+1;
int mid=l+((r-l)>>1);
LL sum=0;
if(mid>=L) sum=sum+query(L,R,l,mid,rt<<1);
if(mid+1<=R) sum=sum+query(L,R,mid+1,r,(rt<<1)|1);
return sum;
}
void update(int L,int R,int l,int r,int rt)
{
if(l==r)
{
segTree[rt]=sqrt(segTree[rt]);
return;
}
if(L<=l&&r<=R&&segTree[rt]==r-l+1) return;
int mid=l+((r-l)>>1);
if(L<=mid) update(L,R,l,mid,rt<<1);
if(mid+1<=R) update(L,R,mid+1,r,(rt<<1)|1);
segTree[rt]=segTree[rt<<1]+segTree[(rt<<1)|1];
}
int main()
{
int n,m,L,R,op,cas=0;
while(scanf("%d",&n)!=EOF)
{
build(1,n,1);
printf("Case #%d:\n",++cas);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&op,&L,&R);
if(L>R) swap(L,R);
if(op)
{
printf("%lld\n",query(L,R,1,n,1));
}
else
{
update(L,R,1,n,1);
}
}
printf("\n");
}
}
