线段树课题—HDU 4027 Can you answer these queries

线段树专题—HDU 4027 Can you answer these queries?

题意：给n（1-100000）个点，且所有点的值的和不超过2的63次，然后m（1-100000）个操作，操作有两种，一种把一段区间的每个点的值变为他的开根号的值，另一种是询问一段区间点值的和

分析：先求出最多要更新的次数，然后进行判断，下面是计算：

设一共有n个点，每个点的值一样为k(最极端的情况)，值的总和当做2^63（最极端的和）

那么再设n=2^a,k=2^b

由于n*k=2^63,那么2^a*2^b=2^63，也就是a+b=63

那么一共需要更新的次数就是n*sqrt（b），用上述所得转换一下就是2^a*sqrt(63-a),这个显然到后面是一个递增的，

也就是说当2^a，也就是n取到最大值100000时即可

那么当n=100000时，a=18，b=63-18=45

那么点的总更新次数是sqrt（45）*100000

再算上每次更新需要logm=18的操作复杂度，也就是18*sqrt（45）*100000=12600000，也就是1千万左右的复杂度，题目给的是2ms，可以做用点更新去做

其实大概估计一下最多也就是8*100000*log（100000）

注意：这题比较坑的是他给的区间x和y不一定是[x,y]，也就是x和y大小要判断一下，还有数据要long long表示

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
ll sum[maxn<<2];
void up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        scanf("%I64d",&sum[rt]);
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    up(rt);
}
void update(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R&&sum[rt]==r-l+1) return;
    if(l==r) {
        sum[rt]=sqrt(sum[rt]);
        return;
    }
    int mid =(l+r)>>1;
    if(L<=mid) update(L,R,l,mid,rt<<1);
    if(R>mid) update(L,R,mid+1,r,rt<<1|1);
    up(rt);
}
ll query(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R) return sum[rt];
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid) ans+=query(L,R,l,mid,rt<<1);
    if(R>mid) ans+=query(L,R,mid+1,r,rt<<1|1);
    return ans;
}
int main()
{
    int n;
    int cnt=0;
    while(scanf("%d",&n)!=EOF){
        build(1,n,1);
        int m;
        scanf("%d",&m);
        printf("Case #%d:\n",++cnt);
        while(m--){
            int t,x,y;
            scanf("%d%d%d",&t,&x,&y);
            if(t) printf("%I64d\n",query(min(x,y),max(x,y),1,n,1));
            else update(min(x,y),max(x,y),1,n,1);
        }
        printf("\n");
    }
}