HDU4027(Can you answer these que

链接：https://vjudge.net/contest/260644#problem/H
思路：我们考虑1e18内的数据可以在常数次以内开根号变为1，所以我们维护区间信息时考虑维护区间最大值，如果区间最大值为1的话那么当前区间所有值都为1不用再递归，否则递归左右子树一直到叶节点或者到区间最大值为1的地方，在叶节点更新值，同时pushup回去合并区间信息。注意本题有些很无聊的坑点，输入需要特判一下。

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

const int maxn = 1e5+10;
int maxv[maxn<<2];
long long sum[maxn<<2],a[maxn];
int n,q;

inline void pushup(int o){
  sum[o] = sum[o<<1] + sum[o<<1|1];
  maxv[o] = max(maxv[o<<1],maxv[o<<1|1]);
}


void build(int o,int l,int r){
  if(l<r){
    int mid = l+r>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);
  }
  else{
    sum[o] = a[l];
    maxv[o] = a[l];
  }
}

void update(int o,int tl,int tr,int l,int r){
  if(tr<l||r<tl)return;
  if(maxv[o]==1){
        return;
  }
  if(tr==tl){
      a[tl] = (int)sqrt(a[tl]+0.5);
      maxv[o]  = a[tl];
      sum[o] = a[tl];
      return;
  }
  int mid = (tl+tr)>>1;
  update(o<<1,tl,mid,l,r);
  update(o<<1|1,mid+1,tr,l,r);
  pushup(o);
} 

long long query(int o,int tl,int tr,int l,int r){
  if(tr<l||r<tl)return 0;
  if(l<=tl&&r>=tr)return sum[o];
  //pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  long long ret = query(o<<1,tl,mid,l,r);
  ret+=query(o<<1|1,mid+1,tr,l,r);
  return ret;
}

int main(){
  int kase = 0;
  while(~scanf("%d",&n)){
    printf("Case #%d:\n",++kase);
    memset(maxv,0,sizeof(maxv));
    memset(sum,0,sizeof(sum));
      for(int i=1;i<=n;i++){
          scanf("%lld",&a[i]);
      }
      build(1,1,n);
      scanf("%d",&q);
      for(int i=1;i<=q;i++){
          int d,e,f;
          scanf("%d%d%d",&d,&e,&f);
          if(e>f)swap(e,f);//特判一下
          if(d)printf("%lld\n",query(1,1,n,e,f));
          else update(1,1,n,e,f);
      }
      printf("\n");
  }
  return 0;
}