HDU 4630-No Pain No Game（线段树+离线处理）

题意：

给你n个数的序列a，q个询问，每个询问给l,r，求在下标i在[l，r]的区间任意两个数的最大公约数中的最大值

分析：

有了hdu3333经验，我们从左向右扫序列，如果当前数的约数在前面出现过，那这个约数可能就是最大的答案。所以我们枚举当前数的所有约数，用线段树维护区间最大值，查询序列离线处理保证查询的正确。

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<1|1

#define All 1,N,1

#define N 50010

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

//bef当前数的约数前一次出现的位置

int maxv[N*],n,bef[N],e,a[N],maxn[N];

struct que{

    int l,r,id;

}q[N];

bool cmp(que x,que y){

    return x.r<y.r;

}

void pushup(int rt){

    maxv[rt]=max(maxv[rt<<],maxv[rt<<|]);

}

void build(int l,int r,int rt){

    maxv[rt]=;

    if(l==r)return;

    int m=(l+r)>>;

    build(lson);

    build(rson);

}

void update(int p,int v,int l,int r,int rt){

    if(l==r){

        maxv[rt]=max(maxv[rt],v);

        return;

    }

    int m=(l+r)>>;

    if(p<=m)update(p,v,lson);

    else update(p,v,rson);

    pushup(rt);

}

int query(int L,int R,int l,int r,int rt){

    if(L<=l&&R>=r){

        return maxv[rt];

    }

    int m=(l+r)>>;

    int num=;

    if(L<=m)num=max(num,query(L,R,lson));

    if(R>m)num=max(num,query(L,R,rson));

    return num;

}

void solve(){

    sort(q+,q+e+,cmp);

    memset(bef,,sizeof(bef));

    build(,n,);

    int b=;

    for(int i=;i<=n;++i){

        for(int j=;j*j<=a[i];j++){

            if(a[i]%j==){

                if(bef[j]){

                    update(bef[j],j,,n,);

                }

                int tmp=a[i]/j;

                if(bef[tmp]&&tmp!=j)

                    update(bef[tmp],tmp,,n,);

                bef[j]=i;

                bef[tmp]=i;

            }

        }

        while(b<=e&&q[b].r==i){

            if(q[b].l==q[b].r)

                maxn[q[b].id]=;

            else{

                maxn[q[b].id]=query(q[b].l,q[b].r,,n,);

            }

            b++;

        }

    }

    for(int i=;i<=e;++i)

        printf("%d\n",maxn[i]);

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        for(int i=;i<=n;++i)

            scanf("%d",&a[i]);

            scanf("%d",&e);

        for(int i=;i<=e;++i){

            scanf("%d%d",&q[i].l,&q[i].r);

        q[i].id=i;

        }

        solve();

    }

return ;

}