题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4630
题意：给你n个数据范围在[1,n]中的数，m个操作，每个操作一个询问[L,R],让你求区间[L，R]内任意两个数的最大公倍数。
思路：是线段树是必然的 O.O 。顺着来不好解决，只能离线处理试试。按r从小到大排序，数组a[i]从左到右扫一遍，对每个a[i]都要进行处理，先因数分解，pre[X]表示约数X在前面最后出现的位置。开始处理的是pre[X]到当前位置r都对约数X进行比较更新，后面想想这样是有问题，因为这样不能保证约数X出现在pre[X]与r的中间位置，所以这里我们只对位置pre[X]进行最大约数的比较更新，这样就能很好的解决当询问[pre[X]，r]时，这个约数恰好就出现在区间段内，pre[X]更新为r，起初的对询问区间段r排序能保证这样处理的结果是正确的。
恩，不错，是一道好题。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std; #define lz 2*u,l,mid
#define rz 2*u+1,mid+1,r
const int maxn=;
int maxx[*maxn], flag[*maxn];
int a[maxn];
int pre[maxn];
int n, m, T;
vector<int>vt; struct node
{
int l, r, id;
int ans;
friend bool operator<(const node A, const node B)
{
return A.r<B.r;
}
}f[maxn]; bool cmp(node A, node B)
{
return A.id<B.id;
} void push_down(int u, int l, int r)
{
if(flag[u])
{
flag[*u]=max(flag[*u],flag[u]);
flag[*u+]=max(flag[*u+],flag[u]);
maxx[*u]=max(maxx[*u],flag[u]);
maxx[*u+]=max(maxx[*u+],flag[u]);
flag[u]=;
}
} void Update(int u, int l, int r, int tl, int tr, int val)
{
maxx[u]=max(maxx[u],val);
if(tl<=l&&r<=tr)
{
flag[u]=max(flag[u],val);
maxx[u]=max(maxx[u],val);
return ;
}
push_down(u,l,r);
int mid=(l+r)>>;
if(tr<=mid) Update(lz,tl,tr,val);
else if(tl>mid) Update(rz,tl,tr,val);
else
{
Update(lz,tl,mid,val);
Update(rz,mid+,tr,val);
}
} int Query(int u, int l, int r, int tl, int tr)
{
if(tl<=l&&r<=tr) return maxx[u];
push_down(u,l,r);
int mid=(l+r)>>;
if(tr<=mid) return Query(lz,tl,tr);
else if(tl>mid) return Query(rz,tl,tr);
else
{
int t1=Query(lz,tl,mid);
int t2=Query(rz,mid+,tr);
return max(t1,t2);
}
} void Solve(int x, int r)
{
vt.clear();
vt.push_back(x);
for(int i=; i*i<=x; i++)
if(x%i==)
{
vt.push_back(i);
vt.push_back(x/i);
}
for(int i=; i<vt.size(); i++)
{
int l=pre[ vt[i] ];
pre[ vt[i] ]=r;
if(l==-||l==r) continue;
Update(,,n,l,l,vt[i]);
}
} int main()
{
cin >> T;
while(T--)
{
cin >> n;
for(int i=; i<=n; i++) scanf("%d", a+i), pre[i]=-;
cin >> m;
for(int i=; i<=m; i++) f[i].id=i, scanf("%d%d",&f[i].l,&f[i].r);
sort(f+,f+m+);
for(int i=; i<=*n; i++) maxx[i]=, flag[i]=;
int i=, j=;
while(j<=m)
{
if(i<=f[j].r&&i<=n)
{
Solve(a[i],i);
i++;
}
else
{
if(f[j].l!=f[j].r)f[j].ans=Query(,,n,f[j].l,f[j].r);
else f[j].ans=;
j++;
}
}
sort(f+,f+m+,cmp);
for(int i=; i<=m; i++)
printf("%d\n",f[i].ans);
}
return ;
}