HDOJ 4027 Can you answer these queries?

此题陷阱多多：数据类型（相应的输入输出）、区间端点可能反序、如果用C提交注意强制转换的格式（int(x)是不对的）；

思路：每次如果开根号的区间内含有未达到0或1的数就一直向下，找到这些数并直接更新一次，这样最多跟新4*N次，加上线段树的复杂度，为4*N*lgN，是最坏情况的复杂度，可能由于开根号耗时较多，总体比较耗时（700ms+），查询的复杂度为lgN。

# include <stdio.h>
# include <math.h>

# define N 100005

# define ls ((r)<<1)
# define rs ((r)<<1|1)
# define mid (((x)+(y))>>1)

typedef long long int LL;

LL n, m;
char bott[N<<2];
LL sum[N<<2];

LL root(LL x)
{
        return (LL)floor(sqrt(x));
}

void update(LL r)
{
    sum[r] = sum[ls] + sum[rs];
    bott[r] = bott[ls] & bott[rs];
}

void build(LL r, LL x, LL y)
{
    bott[r] = 0;
    if (x == y)
    {
        scanf("%I64d", &sum[r]);
        return ;
    }
    build(ls, x, mid);
    build(rs, mid+1, y);
    update(r);
}

void srt(LL r, LL x, LL y, LL s, LL t)
{
    if (s<=x && y<=t)
    {
        if (bott[r]) return ;
        else if (x == y)
        {
            sum[r] = root(sum[r]);
            if (sum[r] < 2) bott[r] = 1;
            return ;
        }
    }
    if (s <= mid) srt(ls, x, mid, s, t);
    if (mid+1 <= t) srt(rs, mid+1, y, s, t);
    update(r);
}

void query(LL r, LL x, LL y, LL s, LL t, LL *ans)
{
    if (s<=x && y<=t)
    {
        *ans += sum[r];
        return ;
    }
    if (s<=mid) query(ls, x, mid, s, t, ans);
    if (mid+1<=t) query(rs, mid+1, y, s, t, ans);
}

void solve(void)
{
    LL i, op, s, t, tmp; LL ans;
    scanf("%I64d", &m);
    for (i = 1; i <= m; ++i)
    {
        scanf("%I64d%I64d%I64d", &op, &s, &t);
        //printf("%I64d %I64d %I64d\n", op, s, t);
        if (s > t) tmp = s, s = t, t = tmp;
        if (op == 0)    srt(1, 1, n, s, t);
        else
        {
            ans = 0;
            query(1, 1, n, s, t, &ans);
            printf("%I64d\n", ans);
        }
    }
}

int main()
{
    LL icase = 0;
    while (~scanf("%I64d", &n))
    {
        printf("Case #%I64d:\n", ++icase);
        build(1, 1, n);
        solve();
        putchar('\n');
    }

    return 0;
}