hdu 4027（线段树）

题意：给定100000个数，两种操作，0 i j表示将i j这段的数字都开根号（向下取整），1 i j表示查询i j之间的所有值的和。。。（所有的和都不超过64位）

解题思路：这题要做区间的开平方操作，2^64最多可以做8次开平方操作，所以对于每个节点最多只有8次操作，这道题如果lazy思想的话就要保存每个区间被开平方的次数，但实际上好像不需要，只要一直找到叶子节点并将其开平方即可。如果整个区间内的数都为1，那么就直接返回即可，不需要再往下递归了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long LL;
const int maxn = 100010;

LL sum[maxn*4];
int n, m;

void PushUp(int rt)
{
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    return ;
}

void build(int l, int r, int rt)
{

    sum[rt] = 0;
    if(l == r)
    {
        scanf("%I64d", &sum[rt]);
        return ;
    }
    int m = (l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}

void update(int L, int R, int l, int r, int rt)
{
    if(l == r)
    {
        sum[rt] = sqrt(1.0 * sum[rt]);
        return ;
    }
    if(L<=l && r<=R && sum[rt]==r-l+1) return ;
    int m = (l + r)>>1;
    if(L <= m) update(L, R, lson);
    if(m < R) update(L, R, rson);
    PushUp(rt);
}

LL query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R)
        return sum[rt];
    int m = (l + r)>>1;
    LL ans = 0;
    if(L <= m)   ans += query(L, R, lson);
    if(m < R)    ans += query(L, R, rson);
    return ans;
}

int main()
{
    int test = 0;
    while(scanf("%d", &n) != EOF)
    {
        build(1, n, 1);
        int a, b, c;
        int x, y;
        scanf("%d", &m);
        printf("Case #%d:\n", ++test);
        while(m--)
        {
            scanf("%d%d%d", &a, &b, &c);
            x = min(b, c);
            y = max(b, c);
            if(a == 0)
            {
                update(x, y, 1, n, 1);
            }
            else
            {
                printf("%I64d\n", query(x, y, 1, n, 1));
            }
        }
        puts("");
    }
    return 0;
}