题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4027
题目大意：有n个战舰都排成一排。我们可以使用我们的秘密武器来使一个区间每个战舰的耐力变成到其原始耐力值的平方根。

输入包含几个测试用例，由EOF终止。
第一行输入一个整数n
第二行包含n个整数Ei，表示从战斗开始到结束的每艘战列舰的耐久值。您可以假设所有耐力值的总和小于2^63。
下一行包含一个整数M，表示操作和查询的数量。（1 <= M <= 100000）
对于以下M行，每行包含三个整数T，X和Y
T = 0表示秘密武器的行动，这将降低第X和第Y战列舰之间的战列舰的耐力值，
T = 1表示指挥官的询问，其询问第X和第Y之间的战列舰的耐力值的总和。

思路：很简单，就是用add标记，记录这个区间的开方的次数。对于一个查询，把所有的标记推到叶节点，并且开add次方就可以了。然而就T了。
优化：因为开方到最后值为1，此时再开方，值不再改变了，所以当sum[i]=r-l+1时，就不用再更新，但是要得到sum[i],那么每次更新都必须推到叶节点。这样才能维护sum[i]。然后改完，提交，运行时错误。
最后知道X和Y的大小不确定，就是可能X>Y或者Y>X。这个明显是坑爹。

思考：以后函数把X和Y的大小判断一下，不知道出题人会用什么方式卡你。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

#define MAX_NODE 4000005
#define MAX_ 1000005

struct NODE
{
    int l, r;

}node[MAX_NODE];
int f[MAX_];     //记录节点i的node结构体数组下标f[i]
ll sum[MAX_NODE];//维护区间的值(和)
ll add[MAX_NODE];

void BT(int i, int l ,int r)   //建树
{
    node[i].l=l;
    node[i].r=r;
    sum[i]=0;
    add[i]=0;
    if(l==r)                   //根节点
    {
        f[l]=i;
        scanf("%lld",&sum[i]);
        return;
    }
    BT((i<<1), l, (l+r)/2);    //建左子树
    BT((i<<1)+1, (l+r)/2+1, r);//建右子树

    /***************/

    sum[i]=sum[(i<<1)]+sum[(i<<1)+1];

    /***************/

}

void UP(int i, int l, int r, int c)//更新
{
    if(sum[i]==r-l+1)
    {
        return;
    }
    if(node[i].l==node[i].r)//找到更新区间
    {
        sum[i]=(ll)sqrt(sum[i]);        //更新sum

        return;
    }

    int mid=(node[i].l+node[i].r)/2;//继续寻找区间
    if(r<=mid)                    //全在左区间
    {
        UP(i<<1, l, r, c);
    }
    else if(l>mid)                //全在右区间
    {
        UP((i<<1)+1, l, r, c);
    }
    else
    {
        UP(i<<1, l, mid, c);
        UP((i<<1)+1, mid+1, r, c);
    }
    /**************/
    sum[i]=sum[(i<<1)]+sum[(i<<1)+1];
    /**************/

}

/*************/
ll ans=0;                     //记录每次的查询结果
/*************/

void FD(int i, int l, int r)   //查找
{
    if(node[i].l==l&&node[i].r==r)
    {
        /************/
        ans+=(ll)sum[i];           //维护查询值
        /************/

        return;
    }

    int mid=(node[i].l+node[i].r)/2;//继续查询区间
    if(r<=mid)                    //全在左区间
    {
        FD(i<<1, l, r);
    }
    else if(l>mid)                //全在右区间
    {
        FD((i<<1)+1, l, r);
    }
    else                          //左右区间都有
    {
        FD(i<<1, l, mid);
        FD((i<<1)+1, mid+1, r);
    }

}

/*********************/
//建树 BT(1, 1 ,n);节点1-n
//查询 FD(1, a, b);[a, b]的信息
//更新 UP(1, a, b, c);//把区间的add+=a

int main()
{
    int cut=1, n, m;
    while(scanf("%d",&n)!=EOF)
    {
        printf("Case #%d:\n",cut);
        BT(1, 1, n);
        scanf("%d",&m);
        while(m--)
        {
            int a, b, c;
            scanf("%d%d%d",&a,&b,&c);
            if(b>c)
            {
                swap(b, c);
            }
            if(a==0)
            {
                UP(1, b, c, 1);
            }
            else
            {
                ans=0;
                FD(1, b, c);
                printf("%lld\n",ans);
            }
        }
        printf("\n");
        cut++;
    }

    return 0;
}