HDU-4630 No Pain No Game 树状数组+离线操作-白红宇

HDU-4630 No Pain No Game 树状数组+离线操作

阅读量：4693 次

发布时间：2019-06-09

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

　　题目链接：

　　题意：给一个数列，询问区间[l,r]里两个数最大gcd。

　　求区间的最大gcd(a,b)，就是找一个数是在这个区间所有数的约数中，至少出现两次，而且最大的那个数。那么接下来就比较容易了，从右到左扫描数列，用pre[i]表示约数 i 在当前这个位置往右第一次出现的位置，那么每到一个位置枚举num[i]的所有约数，然后用树状数组维护一个区间最大值就行了，用树状数组维护区间最大值有点麻烦，但这里是从右往左扫描的，因此可以求0-i点的最大值，就很简单了。。。

1 //STATUS:C++_AC_546MS_1596KB  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 //#include 
        
           6 #include 
         
            7 #include 
          
            8 #include 
           
             9 #include 
            
              10 #include 
             
               11 #include 
              
                12 #include 
               
                 13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 #include 
                   
                     17 #include 
                    
                      18 #include 
                     
                       19 #include 
                      
                        20 #include 
                       
                         21 #include 
                        
                          22 #include 
                          23 using namespace std; 24 //#pragma comment(linker,"/STACK:102400000,102400000") 25 //using namespace __gnu_cxx; 26 //define 27 #define pii pair
                          
                            28 #define mem(a,b) memset(a,b,sizeof(a)) 29 #define lson l,mid,rt<<1 30 #define rson mid+1,r,rt<<1|1 31 #define PI acos(-1.0) 32 //typedef 33 typedef __int64 LL; 34 typedef unsigned __int64 ULL; 35 //const 36 const int N=50010; 37 const int INF=0x3f3f3f3f; 38 const int MOD=10007,STA=8000010; 39 const LL LNF=1LL<<60; 40 const double EPS=1e-8; 41 const double OO=1e15; 42 const int dx[4]={-1,0,1,0}; 43 const int dy[4]={ 0,1,0,-1}; 44 const int day[13]={ 0,31,28,31,30,31,30,31,31,30,31,30,31}; 45 //Daily Use ... 46 inline int sign(double x){ return (x>EPS)-(x<-EPS);} 47 template
                           
                             T gcd(T a,T b){ return b?gcd(b,a%b):a;} 48 template
                            
                              T lcm(T a,T b){ return a/gcd(a,b)*b;} 49 template
                             
                               inline T lcm(T a,T b,T d){ return a/d*b;} 50 template
                              
                                inline T Min(T a,T b){ return a
                               
                                 inline T Max(T a,T b){ return a>b?a:b;} 52 template
                                
                                  inline T Min(T a,T b,T c){ return min(min(a, b),c);} 53 template
                                 
                                   inline T Max(T a,T b,T c){ return max(max(a, b),c);} 54 template
                                  
                                    inline T Min(T a,T b,T c,T d){ return min(min(a, b),min(c,d));} 55 template
                                   
                                     inline T Max(T a,T b,T c,T d){ return max(max(a, b),max(c,d));} 56 //End 57 58 struct Node { 59 int l,r,id; 60 bool operator < (const Node& a)const { 61 return l>a.l; 62 } 63 }nod[N]; 64 int num[N],ans[N],pre[N],hig[N]; 65 int T,n,m; 66 67 inline int lowbit(int x) 68 { 69 return x&(-x); 70 } 71 72 void update(int x,int val) 73 { 74 while(x<=n){ 75 hig[x]=Max(hig[x],val); 76 x+=lowbit(x); 77 } 78 } 79 80 int getmax(int x) 81 { 82 int ret=0; 83 while(x){ 84 ret=Max(ret,hig[x]); 85 x-=lowbit(x); 86 } 87 return ret; 88 } 89 90 int main(){ 91 // freopen("in.txt","r",stdin); 92 int i,j,k,up; 93 scanf("%d",&T); 94 while(T--) 95 { 96 scanf("%d",&n); 97 for(i=1;i<=n;i++){ 98 scanf("%d",&num[i]); 99 }100 scanf("%d",&m);101 for(i=0;i
                                    
                                     =1;i--){109 for(j=1;j*j<=num[i];j++){110 if(num[i]%j==0){111 if(pre[j])update(pre[j],j);112 pre[j]=i;113 if(j*j==num[i])continue;114 int t=num[i]/j;115 if(pre[t])update(pre[t],t);116 pre[t]=i;117 }118 }119 for(;nod[k].l==i;k++){120 ans[nod[k].id]=getmax(nod[k].r);121 }122 }123 124 for(i=0;i

转载于:https://www.cnblogs.com/zhsl/p/3234099.html

你可能感兴趣的文章

git: fatal: Not a git repository (or any of the parent directories): .git