HDU 4027 Can you answer these queries?(线段树区间更新)

题目链接：

戳我

题目大意：

一组数字，１....n，数字范围是  1 到　2^63 有两种操作，

０x y　代表　从ｘ到ｙ，每个数都开平方

１ x y　代表　从ｘ到ｙ所有数的和

样例解释

略

解题思路：

一个数不停的开平方，肯定有　变成　１　的时候，当一个数是１时，在开平方就没有意义了，所以对于一个区间都是１的，要标记掉，这样更新的时候就节省时间了，如果这个区间不全是１，就暴力做。

代码：

//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
#define LL long long
using namespace std;

const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;

struct Node
{
    int l, r;
    LL sum;
    int flag;
}tree[maxn << 2];

void Build(int i, int l, int r)
{
    tree[i].l = l;
    tree[i].r = r;
    tree[i].flag = 0;
    if(l == r)
    {
        scanf("%lld", &tree[i].sum);
        return;
    }
    int mid = (l + r) >> 1;
    Build(i<<1, l, mid);
    Build(i<<1|1, mid+1, r);
    tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
}

void PushDown(int i)
{
    if(tree[i].flag)
        return;
    if(tree[i].l == tree[i].r)
    {
        tree[i].sum = sqrt(tree[i].sum);
        if(tree[i].sum == 1)
        {
            tree[i].flag = 1;
        }
        return;
    }
    else 
    {
        PushDown(i<<1);
        PushDown(i<<1|1);
        tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
        tree[i].flag = tree[i<<1].flag & tree[i<<1|1].flag;
    }
}
void Update(int i, int l, int r)
{
    //printf("i = %d l = %d r = %d
", i, l, r);
    if(tree[i].r == r && l == tree[i].l)
    {
        PushDown(i);
        return;
    }
    int mid = (tree[i].r + tree[i].l) >> 1;
    if(r <= mid)
    {
        Update(i<<1, l, r);
    }
    else if(l > mid)
    {
        Update(i<<1|1, l, r);
    }
    else
    {
        Update(i<<1, l, mid);
        Update(i<<1|1, mid+1, r);
    }
    tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
    tree[i].flag = tree[i<<1].flag & tree[i<<1|1].flag;
 
}

LL Query(int i, int l, int r)
{
   if(tree[i].l == l && tree[i].r == r)
    {
        return tree[i].sum;
    }
    int mid = (tree[i].r + tree[i].l) >> 1;
    if(r <= mid)
    {
        return Query(i<<1, l, r);
    }
    else if(l > mid)
    {
        return Query(i<<1|1, l, r);
    }
    else
    {
        return Query(i<<1, l, mid) + Query(i<<1|1, mid+1, r);
    }
}

int main()
{
    int n, m;
    int op, x, y;
    int tt = 1;
    while(~scanf("%d", &n))
    {
        Build(1, 1, n);
        printf("Case #%d:
", tt++);
        scanf("%d", &m);
        while(m--)
        {
            scanf("%d %d %d", &op, &x, &y);
            if(x>y)   //这里真坑,不然一直re
                swap(x,y);  
            if(op)
            {
                printf("%lld
", Query(1, x, y));
            }
            else
            {
                Update(1, x, y);
            }
        }
        printf("
");
    }
    return 0;
}