HDU 5869 Different GCD Subarray Query-白红宇

HDU 5869 Different GCD Subarray Query

阅读量：7039 次

发布时间：2019-06-28

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

离线操作，树状数组，$RMQ$。

这个题的本质和$HDU$ $3333$是一样的，$HDU$ $3333$要求计算区间内不同的数字有几个。

这题稍微变了一下，相当于原来扫描到$i$的之后是更新$a[i]$的情况，现在是更新$log$级别个数的数字（因为以$i$为结尾的区间，最多只有$log$级别种不同的$gcd$）。

求区间$gcd$可以用$RMQ$预处理一下，然后就可以$O(1)$查询了。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template 
               
                inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}}const int maxn=100000+10;int T,n,Q,a[maxn],dp[maxn][30],c[maxn],pre[maxn*10],ans[maxn];struct X{ int L,R,id;}s[maxn];int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); }void RMQ_init(){ for(int i=0;i
                
                 0;i=i-lowbit(i)) res=res+c[i]; return res;}void update(int x,int v){ for(int i=x;i<=n;i=i+lowbit(i)) c[i]=c[i]+v;}int main(){ while(~scanf("%d%d",&n,&Q)) { for(int i=0;i
                 
                  pos2) continue; if(pre[g]!=0) update(pre[g],-1); update(pos2,1); pre[g]=pos2; pos1--,pos2--; R=pos1-1; if(R<0) break; g=RMQ(R,i); } while(p