HDU4027(Can you answer these queries?)-白红宇

HDU4027(Can you answer these queries?)

阅读量：4972 次

发布时间：2019-06-12

本文共 1868 字，大约阅读时间需要 6 分钟。

题目链接:

题目大意:有一个长度为n的数组，有m次操作，每次操作输入 v x y，v==0时x~y区间内的数都开平方并且向下取整，v==1时求x~y区间内所有数的和。

题目思路:long long范围内的数开平方不超过7次就会变成1，所以我们更新的时候只需看x~y区间内的和是不是等于区间的长度(区间内所有数都为1)，是的话

不用更新了直接return，否则继续向下更新，这道题坑就坑在x，y大小不确定，需要自己判断处理（QAQ），这里TLE半天

这道题给我更大的收获是线段树不需要用struct，直接用数组模拟就行，方便高效，新技能get。ICPC，fighting！

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #define lson root<<1,l,mid#define rson root<<1|1,mid+1,r#define fi first#define se second#define ping(x,y) ((x-y)*(x-y))#define mst(x,y) memset(x,y,sizeof(x))#define mcp(x,y) memcpy(x,y,sizeof(y))#define Min(x,y) (x
                   
                    y?x:y)using namespace std;#define gamma 0.5772156649015328606065120#define MOD 100000007#define inf 0x3f3f3f3f#define N 100005#define maxn 10001000typedef long long LL;typedef pair
                    
                      PII;LL node[N<<2];int x,y;void build(int root,int l,int r){ if(l==r){ scanf("%lld",&node[root]); return; } int mid=l+r>>1; build(lson); build(rson); node[root]=node[root<<1]+node[root<<1|1];}void add(int root,int l,int r){ if(x<=l&&r<=y&&node[root]==r-l+1) return; if(l==r){node[root]=sqrt(node[root]);return;} int mid=l+r>>1; if(y<=mid) add(lson); else if(x>mid) add(rson); else{ add(lson); add(rson); } node[root]=node[root<<1]+node[root<<1|1];}LL query(int root,int l,int r){ if(x<=l&&r<=y) return node[root]; int mid=l+r>>1; if(y<=mid) return query(lson); else if(x>mid) return query(rson); else return query(lson)+query(rson);}int main(){ int n,m,i,j,v,group,Case=0; LL ans; while(~scanf("%d",&group)){ printf("Case #%d:\n",++Case); build(1,1,group); scanf("%d",&m); for(i=0;i
                     
                      y) x^=y^=x^=y; if(!v) add(1,1,group); else printf("%lld\n",query(1,1,group)); } printf("\n"); } return 0;}

转载于:https://www.cnblogs.com/Kurokey/p/5411989.html

你可能感兴趣的文章