Different GCD Subarray Query HDU - 5869

解法

以一个数字结尾的所有连续段gcd，不会超过log个，想象一下一个gcd的唯一分解，每次要产生新的gcd，肯定是从老的gcd去掉一些质因子，也就是说至少会去掉>=2的数，gcd至少变成1/2，是呈指数型减少的。
将询问的区间按照r从小到大排序。然后从左往右扫数组，扫到下标i的时候，就记录所有出现过的gcd，它所在连续段最大左端点。并在树状数组上做标记。

如图，有4个不同的gcd，其最大的右端点就在g1,g2,g3,g4的位置，我们查询[L,R]的时候就是看这个区间内有多少个左端点。在后面继续遍历数组的时候，gcd有可能是新的gcd，也有可能是以前出现过的gcd，都要将其左端点更新到最大位置。在树状数组中把原来的标记去掉，在新的位置打上标记

代码

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll maxM = 1e6+10;
const ll inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}

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

int N,Q;
struct Qu{
    int l,r,id;
    bool operator < (const Qu &o) const{
        return r < o.r;
    } 
}qu[100010];
int a[maxn];
map<int,int> mp1;//i-1的gcd，mp基础不同gcd出现的最大左端点的位置
map<int,int> mp2;//i的gcd
ll ans[maxn];
ll tr[maxn];
map<int,int> pos; // 记录位置
void add(int x,int v){
    for(int i = x;i<=1000000;i += (i&-i))
        tr[i] += v;
}
ll query(int r){
    ll sum = 0;
    for(int i = r;i>=1;i -= (i&-i))
        sum += tr[i];
    return sum;
}
void solve(){
    int now = 1;
    sort(qu+1,qu+Q+1);
    mp1.clear();mp2.clear();
    for(int i = 1;i<=N;i++){
        swap(mp1,mp2);
        mp2.clear();
        mp2[a[i]] = i;
        for(auto p:mp1){
            int g = p.fs,idx = p.sc;
            mp2[gcd(g,a[i])] = max(mp2[gcd(g,a[i])],idx);
        }
        for(auto p:mp2){
            int g = p.fs,idx = p.sc;
            if(pos[g] == 0){
                pos[g] = idx;
                add(idx,+1);
            }else if(pos[g] < idx){
                add(pos[g],-1);
                add(idx,+1);
                pos[g] = idx;
            }
        }
        while(qu[now].r  ==  i && now <= Q){
            ans[qu[now].id] = query(qu[now].r) - query(qu[now].l-1);
            now++;
        }
    }

    for(int i = 1;i<=Q;i++){
        printf("%lld\n",ans[i]);
    }
}
void init(){
    pos.clear();
    for(int i = 1;i<=N;i++) tr[i] = 0;
}
int main(){
    // debug_in;

    while(scanf("%d %d",&N,&Q)!=EOF){
        init();
        for(int i = 1;i<=N;i++) read(a[i]);
        for(int i = 1;i<=Q;i++){
            read(qu[i].l,qu[i].r);
            qu[i].id = i;
        }

        solve();
    }





    return 0;
}