[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query

题目链接

题意：

给定 $N$ 个数字， $Q$ 次询问，每次询问为查询下标在 $[l,r]$ 之间的所有数字中所有可能的子段的 $gcd$ 有多少种。$N,Q < 10^5 , a_i < 10^6$

题解：

首先一个重要的结论：以固定点为结尾的子段的 $gcd$ 种数不超过 $max(n,log(max(a_i)))$ 证明：每次往原有的序列里加入一个数字的话， $gcd$ 要么不变，要么至少变为原来的1/2，因此为指数级减小。

有了这个结论，我们可以试着来枚举一个端点考虑本题，不妨枚举每个段的右端点$r_j$ , 假设集合$S$表示以$r_{j-1}$ 为结尾的所有 $gcd$ ，那么要求出以$r_j$为结尾的所有 $gcd$ ，只需遍历S中的每个数字$d_k$，计算其与$a_j$ 的 $gcd$ ，放入新集合$S^{‘}$即可。这样的话我们可以得到一个空间为$O(nlogn)$的结果，表示以每个点为结尾的所有段的 $gcd$ 都是哪些数字。

现在来考虑查询。每次查询的话是要求出来$[l,r]$之间所有可能的 $gcd$ 。直接暴力不可取，由上面的结果可以试着考虑能否转化为前缀问题。可以发现，如果我们对所有的$[l,r]$离线处理，按$r$从小到大排序，并且按照这个顺序来调整已经遇到过的 $gcd$ 的信息的话，每次的查询只需要考虑有多少个 $gcd$ 出现的最右左端点大于等于l，这句话具体的意思是，一个 $gcd$ 可能出现过了很多次，不同的段都可以得到这个 $gcd$ ，但是我们只考虑这些段中左端点l_j最大的那个点$p_j$，这样的话如果$l<=p_j$那么可以确定$[l,r]$中一定有这个 $gcd$ （种类+1），这就就转化成了一个计数问题。

那么考虑如何来维护这个每个 $gcd$ 及其最右左端点。从我们推$O(nlogn)$的以每个点位结尾的 $gcd$ 集合来看，只需要在这个过程中为每个 $gcd$ 多维护一个表示最右左端点的域即可，更新就是把每次新产生的（以前从来没有见过的） $gcd$ 的这个域设为当前的下标i，其他的保持不变即可。由于$a_i$的最大值只有$10^6$，可以直接用一个数组$has[d]$来维护到目前为止$d$作为某个段的 $gcd$ 出现的最右位置。至于前后集合的递推可以用滚动数组，考虑到去重的话用两个$map$替代两个数组即可。

代码的话想清楚之后实现还是很简单的。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;
typedef long long ll;
int N,Q,MX;
map<int,int> mp[2];
map<int,int>::iterator it;
int has[maxn*10];

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

vector<pair<int,int> > qs[maxn];
int tr[maxn*20];
void change(int x,int p){
    while(x<=MX){
        tr[x]+=p;
        x+=(x&(-x));
    }
}
ll sum(int x){
    ll res=0;
    while(x>0){
        res+=tr[x];
        x-=(x&(-x));
    }
    return res;
}
void move(int a,int b){
    change(a,-1);
    change(b,1);
}
int a[maxn],ans[maxn];
void init(){
    for(int i=0;i<=N;i++) qs[i].clear();
    mp[0].clear(),mp[1].clear();//final error
    memset(tr,0,sizeof(tr));
    memset(has,0,sizeof(has));
    MX=0;
}
int main(){
    int l,r,tmp,id,pt,pos;
    while(~scanf("%d%d",&N,&Q)){
        init();pt=0;
        for(int i=1;i<=N;i++){
            scanf("%d",&a[i]);
            MX=max(MX,a[i]);
        }
        for(int i=1;i<=Q;i++){
            scanf("%d%d",&l,&r);
            qs[r].push_back(make_pair(l,i));
        }
        
        for(int i=1;i<=N;i++,pt^=1){
            int len=qs[i].size();
            mp[pt].clear();
            mp[pt][a[i]]=i;
            for(it=mp[pt^1].begin();it!=mp[pt^1].end();++it){   
                tmp=gcd(a[i],it->first);
                if(mp[pt].find(tmp)!=mp[pt].end()){
                    mp[pt][tmp]=max(mp[pt][tmp],it->second);
                }else{
                    mp[pt][tmp]=it->second;
                }
            }
            for(it=mp[pt].begin();it!=mp[pt].end();++it){
                tmp=it->first,pos=it->second;
                if(has[tmp]){
                    if(has[tmp]==pos) continue;
                    move(min(has[tmp],pos),max(has[tmp],pos));
                    has[tmp]=max(has[tmp],pos);
                }else{
                    change(pos,1);
                    has[tmp]=pos;
                }
            }
            if(len){
                for(int j=0;j<len;j++){
                    l=qs[i][j].first,id=qs[i][j].second;
                    ans[id]=sum(i)-sum(l-1);
                }
            }
        }
        for(int i=1;i<=Q;++i){
            printf("%d\n",ans[i]);//error2
        }
    }
    
    return 0;
}