HDU 4630(ツリー配列、オフライン)

題意はあなたに1-nの配列をあげて、qに質問して、各質問区間の中の最大gcdを求めます.
各数の因数を先に処理する.そして,問合せの右区間に従ってソートし,現在の問合せまでの最左境界を記録し,ある因子の最右,次右位置を,この因子の位置が更新されるたびに木状配列で維持する.

#include <bits/stdc++.h>
using namespace std;
#define maxn 51111

vector <int> fac[maxn]; //      
int num[maxn], c[maxn], a[maxn], n;
int pre[maxn][2]; // i     ，    
struct node {
    int l, r, ans, id;
    bool operator < (const node &a) const {
        return r < a.r || (r == a.r && l > a.l);
    }
}qu[maxn];
bool cmp (const node &a, const node &b) {
    return a.id < b.id;
}

int lowbit (int x) {
    return x&(-x);
}

void add (int pos, int num) {
    for (int i = pos; i > 0; i -= lowbit (i)) {
        c[i] = max (c[i], num);
    }
}

int query (int pos) {
    int ans = 0;
    for (int i = pos; i <= n; i+= lowbit (i)) {
        ans = max (ans , c[i]);
    }
    return ans;
}

void solve (int pos) {
    int kk = a[pos];
    for (int i = 0; i < fac[kk].size (); i++) {
        int v = fac[kk][i];
        //++num[v];
        if (pre[v][0] < pos) {
            pre[v][1] = pre[v][0];
            pre[v][0] = pos;
        }
        else if (pre[v][1] < pos) {
            pre[v][1] = pos;
        }
        if (pre[v][1] != -1) {
            add (pre[v][1], v);
        }
    }
}

int main () {
    //freopen ("in", "r", stdin);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    for (int i = 1; i <= 50000; i++) {
        fac[i].clear ();
    }
    for (int i = 1; i <= 50000; i++) {
        for (int j = i; j <= 50000; j+= i)
            fac[j].push_back (i);
    }
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        int q; cin >> q;
        for (int i = 1; i <= q; i++) {
            cin >> qu[i].l >> qu[i].r;
            qu[i].id = i;
        }
        sort (qu+1, qu+1+q);
        memset (c, 0, sizeof c);
        memset (num, 0, sizeof num);
        memset (pre, -1, sizeof pre);
        int pre_l, pre_r;
        for (int i = 1; i <= q; i++) {
            if (i == 1) {
                pre_r = qu[i].r, pre_l = qu[i].l;
                for (int pos = qu[i].r; pos >= qu[i].l; pos--) {
                    solve (pos);
                }
            }
            else {
                for (int j = qu[i].r; j >= pre_r+1; j--) {
                    solve (j);
                }
                for (int j = pre_l-1; j >= qu[i].l; j--) {
                    solve (j);
                }
            }
            qu[i].ans = query (qu[i].l);
            pre_l = min (pre_l, qu[i].l);
            pre_r = qu[i].r;
        }
        sort (qu+1, qu+1+q, cmp);
        for (int i = 1; i <= q; i++)
            cout << qu[i].ans << endl;
    }
    return 0;
}