hdu5381 The sum of gcd]莫队算法

题意：http://acm.hdu.edu.cn/showproblem.php?pid=5381

思路：这个题属于没有修改的区间查询问题，可以用莫队算法来做。首先预处理出每个点以它为起点向左和向右连续一段的gcd发生变化的每个位置，不难发现对每个点A[i]，这样的位置最多logA[i]个，这可以利用ST表用nlognlogA[i]的时间预处理，然后用二分+RMQ在nlogn的时间内得到。然后就是区间变化为1时的转移了，不难发现区间变化为1时，变化的答案仅仅是以变化的那一个点作为左端点或右端点的连续子串的gcd的和，而这个gcd最多logA[i]种，利用前面的预处理可以在logA[i]的时间内累加得到答案。总复杂度O(NlogNlogA[i]+N√NlogA[i])

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define X                   first
#define Y                   second
#define pb                  push_back
#define mp                  make_pair
#define all(a)              (a).begin(), (a).end()
#define fillchar(a, x)      memset(a, x, sizeof(a))
#define copy(a, b)          memcpy(a, b, sizeof(a))

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

//#ifndef ONLINE_JUDGE
void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);}
void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R>
void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1;
while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>
void print(const T t){cout<<t<<endl;}template<typename F,typename...R>
void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>
void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}
//#endif
template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);}
template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}

const double PI = acos(-1.0);
const int INF = 1e9 + 7;
const double EPS = 1e-8;

/* -------------------------------------------------------------------------------- */

const int maxn = 1e4 + 7;

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

struct ST {
    int dp[maxn][20];
    int index[maxn];
    void init_index() {
        index[1] = 0;
        for (int i = 2; i < maxn; i ++) {
            index[i] = index[i - 1];
            if (!(i & (i - 1))) index[i] ++;
        }
    }
    void init_gcd(int a[], int n) {
        for (int i = 0; i < n; i ++) dp[i][0] = a[i];
        for (int j = 1; (1 << j) <= n; j ++) {
            for (int i = 0; i + (1 << j) - 1 < n; i ++) {
                dp[i][j] = gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int query_gcd(int L, int R) {
        int p = index[R - L + 1];
        return gcd(dp[L][p], dp[R - (1 << p) + 1][p]);
    }
};
ST st;

int n, q, block;
int a[maxn];
vector<int> L[maxn], R[maxn];
pair<pii, int> b[maxn];

bool cmp(const pair<pii, int> &a, const pair<pii, int> &b) {
    int lb = a.X.X / block, rb = b.X.X / block;
    return lb == rb? a.X.Y < b.X.Y : lb < rb;
}

void init() {
    for (int i = 0; i < n; i ++) {
        L[i].clear();
        R[i].clear();
    }
    for (int i = 0; i < n; i ++) {
        int u = i;
        R[i].pb(i - 1);
        while (u < n) {
            int l = u, r = n - 1;
            while (l < r) {
                int m = (l + r + 1) >> 1;
                if (st.query_gcd(i, m) == st.query_gcd(i, u)) l = m;
                else r = m - 1;
            }
            u = l + 1;
            R[i].pb(l);
        }
    }
    for (int i = 0; i < n; i ++) {
        int u = i;
        L[i].pb(i + 1);
        while (u >= 0) {
            int l = 0, r = u;
            while (l < r) {
                int m = (l + r) >> 1;
                if (st.query_gcd(m, i) == st.query_gcd(u, i)) r = m;
                else l = m + 1;
            }
            u = l - 1;
            L[i].pb(l);
        }
    }
}

ll f(int l, int r) {
    ll ans = 0;
    for (int i = 1; i < R[l].size(); i ++) {
        if (r <= R[l][i]) return ans + (ll)(r - R[l][i - 1]) * st.query_gcd(l, r);
        ans += (ll)(R[l][i] - R[l][i - 1]) * st.query_gcd(l, R[l][i]);
    }
}

ll g(int l, int r) {
    ll ans = 0;
    for (int i = 1; i < L[r].size(); i ++) {
        if (l >= L[r][i]) return ans + (ll)(L[r][i - 1] - l) * st.query_gcd(l, r);
        ans += (ll)(L[r][i - 1] - L[r][i]) * st.query_gcd(L[r][i], r);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int T;
    cin >> T;
    st.init_index();
    while (T --) {
        cin >> n;
        block = (int)sqrt(n + 0.1);
        for (int i = 0; i < n; i ++) {
            scanf("%d", a + i);
        }
        st.init_gcd(a, n);
        init();
        cin >> q;
        for (int i = 0; i < q; i ++) {
            scanf("%d%d", &b[i].X.X, &b[i].X.Y);
            b[i].X.X --;
            b[i].X.Y --;
            b[i].Y = i;
        }
        sort(b, b + q, cmp);
        vector<ll> ans(q);
        ll lastans = a[0];
        int lastl = 0, lastr = 0;
        /** 注意区间变化的顺序，优先考虑扩大区间，保证任何时刻区间不为负 */
        for (int i = 0; i < q; i ++) {
            while (lastl > b[i].X.X) {
                lastl --;
                lastans += f(lastl, lastr);
            }
            while (lastr < b[i].X.Y) {
                lastr ++;
                lastans += g(lastl, lastr);
            }
            while (lastl < b[i].X.X) {
                lastans -= f(lastl, lastr);
                lastl ++;
            }
            while (lastr > b[i].X.Y) {
                lastans -= g(lastl, lastr);
                lastr --;
            }
            ans[b[i].Y] = lastans;
        }
        for (int i = 0; i < q; i ++) {
            printf("%I64d
", ans[i]);
        }
    }
    return 0;
}