题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4027

题意：给一个数组序列， 数组长度为100000，现在有两种操作， 一种操作是将某一个固定区间所有数开方（向下取整），另一种操作是询问某个区间的所有数字之和。

看似区间开平方很复杂其实挺简单的，因为10^18开方到1也不用几次所以只要考虑遍历到的区间是否满足区间总和为r-l+1，满足那么便不操作否则

单点更新。即便是如此单点更新也不需要几次大约也能满足总的复杂度为nlogn。这题还有要注意的是给的区间不一定是按大小来的就是说x可能大于y。

#include <iostream>#include <cstring>#include <cmath>#include <cstdio>using namespace std;typedef long long ll;const int M = 1e5 + 10;ll a[M];struct TnT {    int l , r;    ll num;}T[M << 2];void build(int l , int r , int p) {    int mid = (l + r) >> 1;    T[p].l = l , T[p].r = r;    if(T[p].l == T[p].r) {        T[p].num = a[r];        return ;    }    build(l , mid , p << 1);    build(mid + 1 , r , (p << 1) | 1);    T[p].num = T[p << 1].num + T[(p << 1) | 1].num;}void updata(int l , int r , int p) {    int mid = (T[p].l + T[p].r) >> 1;    if(T[p].l == T[p].r && T[p].l >= l && T[p].r <= r) {        T[p].num = (int)sqrt((double)T[p].num);        return ;    }    if(T[p].num == (T[p].r - T[p].l + 1)) {        return ;    }    if(mid >= r) {        updata(l , r , p << 1);    }    else if(mid < l){        updata(l , r , (p << 1) | 1);    }    else {        updata(l , mid , p << 1);        updata(mid + 1 , r , (p << 1) | 1);    }    T[p].num = T[p << 1].num + T[(p << 1) | 1].num;}ll query(int l , int r , int p) {    int mid = (T[p].l + T[p].r) >> 1;    if(T[p].l == l && T[p].r == r) {        return T[p].num;    }    if(mid >= r) {        return query(l , r , p << 1);    }    else if(mid < l) {        return query(l , r , (p << 1) | 1);    }    else {        return query(l , mid , p << 1) + query(mid + 1 , r , (p << 1) | 1);    }}int main() {    int n;    int ans = 0;    while(scanf("%d" , &n) != EOF) {        ans++;        for(int i = 1 ; i <= n ; i++) {            scanf("%lld" , &a[i]);        }        int m;        build(1 , n , 1);        scanf("%d" , &m);        printf("Case #%d:\n" , ans);        while(m--) {            int x , y , z;            scanf("%d%d%d" , &x , &y , &z);            if(y > z) {                int temp = y;                y = z;                z = temp;            }            if(x == 1) {                ll gb = query(y , z , 1);                printf("%lld\n" , gb);            }            if(x == 0) {                updata(y , z , 1);            }        }        printf("\n");    }    return 0;}

hdu 4027 Can you answer these queries?（线段树）