http://acm.hdu.edu.cn/showproblem.php?pid=4630
给的题解没看懂。。搜解题报告看 了N久 终于在cui大神的指点下 搞明白咋回事了
将1-N中的每个数ai的倍数的位置p求出来 它们任意两个p组成的区间内约数至少为ai 在询问的区间L-R中如果存在这样的区间pi-pj 那肯定存在相邻的 然后排好序 相邻的为一个区间l-r保存起来
以r从小到大排序 将输入的询问区间进行离线处理 以R由小到大排序 对于每个区间插入r值比R小的区间 求值时以L为下界求到N 其实就是求到R 到R还快了500多ms。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define N 50005
#define lowbit(x) (x&(-x))
int a[N],p[N],o[N],ans[N],re[N<<],n;
struct node
{
int ll,r,val;
}tt[N*],q[N];
bool cmp(node a,node b)
{
if(a.r==b.r)
return a.ll<b.ll;
return a.r<b.r;
}
void add(int x,int va)
{
while(x>)
{
re[x]=max(re[x],va);
x-=lowbit(x);
}
}
int getsum(int x,int y)
{
int mm=;
while(x<=y)
{
mm = max(mm,re[x]);
x += lowbit(x);
}
return mm;
}
int main()
{
int i,j,t,m;
cin>>t;
while(t--)
{
memset(re,,sizeof(re));
cin>>n;
for(i = ; i <= n ; i++)
{
scanf("%d",&a[i]);
p[a[i]] = i;
re[i] = ;
}
int g,k=;
for(i = ; i <= n/ ;i++)
{
g = ;
for(j = i ; j <= n ; j+=i)
{
o[g++] = p[j];
}
sort(o,o+g);
for(j = ; j < g ; j++)
{
tt[k].ll = o[j-];
tt[k].r = o[j];
tt[k++].val = i;
}
}
sort(tt,tt+k,cmp);
cin>>m;
for(i = ; i <= m ;i++)
{
scanf("%d%d",&q[i].ll,&q[i].r);
q[i].val = i;
}
sort(q+,q+m+,cmp);
int oo=; for(i = ; i <= m ;i++)
{
if(q[i].ll==q[i].r)
{
ans[q[i].val] = ;
continue;
}
for(j = oo ; j < k&&tt[j].r<=q[i].r ; j++)
{
add(tt[j].ll,tt[j].val);
}
ans[q[i].val] = getsum(q[i].ll,q[i].r);
oo = j;
}
for(i = ;i <= m ;i++)
printf("%d\n",ans[i]);
}
return ;
}