HDU4027 Can you answer these queries 线段树区间求和+剪枝 - c++编程基础

给了你n，然后n个数字在一个数组中，接下来m个询问，每个询问三个数字 t,x,y,若t==0，那么修改区间[x,y]的每一个值，变为原来每个位置上的数开根号取整，若t==1，那么对区间[x,y]求和

由于n,m,很大，所以树状数组铁定超时，若直接用线段树来做区间修改，那么也是超时，这类题目没别的方法了，静心剪枝，发现题目给的数据范围为2^63,有没有发现，2^63开根号绝对不需要开10次，就能到1，到1以后就不需要再开了，意思就是若有某个区间[x,y]每一个点的值都为1时，这一段区间事实上是不需要处理的，怎么判断呢，简单，这个区间的和等于区间大小就是了，

都改好了也不TLE了，也不WA了，但是一直RE，搞不懂，直到最后也没搞懂，最后有队友说题目给的区间 [x,y], x的值不一定比y小，所以需要判别一下，题目在交代x,y的取值范围时，确实没有说x

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                    > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; const int N = 100000 + 5; typedef struct Node { int l,r; LL sum; }; Node tree[N * 4]; LL a[N]; int n; void build_tree(int left,int right,int id) { tree[id].l = left; tree[id].r = right; tree[id].sum = 0; if(left == right) { tree[id].sum = a[left]; return; } int mid = (left + right)>>1; build_tree(left,mid,id * 2); build_tree(mid+1,right,id * 2 + 1); tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum; } void update(int left,int right,int id) { if(tree[id].l == left && tree[id].r == right) { if(tree[id].sum ==right - left + 1) return;//区间和等于区间长度没必要更新处理 else if(left == right) { tree[id].sum = sqrt(tree[id].sum * 1.0); return ; } } LL mid = (tree[id].l + tree[id].r)>>1; if(right <= mid) update(left,right,id * 2); else if(left > mid) update(left,right,id * 2 + 1); else { update(left,mid,id * 2); update(mid + 1,right,id * 2 + 1); } tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum; } LL query(int left,int right,int id) { if(tree[id].l == left && tree[id].r == right) return tree[id].sum; int mid = (tree[id].l + tree[id].r)>>1; if(right <= mid) return query(left,right,id * 2); else if(left > mid) return query(left,right,id * 2 + 1); else return query(left,mid,id * 2) + query(mid + 1,right,id * 2 + 1); } int main() { int Case = 0; while(scanf("%d",&n) == 1) { for(int i=1;i<=n;i++) scanf("%I64d",&a[i]); build_tree(1,n,1); int m; scanf("%d",&m); int t,x,y; printf("Case #%d:\n",++Case); while(m--) { scanf("%d %d %d",&t,&x,&y); if(x > y) swap(x,y); if(t == 0) { update(x,y,1); } else { printf("%I64d\n",query(x,y,1)); } } puts(""); } return 0; }