NOIP2018模拟赛 HDU 4630 No Pain No Game 2018 10 9 T1

难度：NOIP+

算法：离线+树状数组

简述题意：

1.1 题目描述
给定一个长度为n 的排列a1; a2; a3; :::; an, 现在有Q 个询问，每次询
问区间[l,r] 内任意选取两个不同的数字能够得到的gcd 的最大值。

1.2 输入
一行两个整数n;Q
接下来一行是一个长度为n 的排列。

1.3 输出
如题目描述所述

1.4 样例输入1
10 5
8 2 4 9 5 7 10 6 1 3
2 10
2 4
6 9
1 4
7 10

1.5 样例输出1
5
2
2
4
3

1.6 数据规模与约定
本题共十个测试点
对于1,2,3 三个测试点总有n;Q  1000.
对于全部测试点有n;Q  105

 题解：

首先，它是一道套路题（我们教练说的，哈哈哈）

离线储存，排序，加上树状数组。

易证，每回都要记录他的因数上一次出现的位置，当然每回更新最大值的时候也是取最大值，

好吧，，，你们听不明白我在说什么，但是我还是要接着说。

然后呢，你需要逆序处理，每次跑树状数组求区间最大值，就好了！

PS；[l, r]  这个数学公式，仿佛l和r可以取到等号！ 

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#define ll long long
#define N 500005
using namespace std;
int a[N],c[N],n;
int lowbit(int x)
{
	return x & -x;
}
void add(int x,int val)
{
	while(x)
	{
		c[x]=max(val,c[x]);
		x-=lowbit(x);
	}
}
int getmax(int x)
{
	int ret=0;
	while(x<=n)
	{
		ret=max(ret,c[x]);
		x+=lowbit(x);
	}
	return ret;
}
struct node
{
	int l,r,idd;
}S[N];
int cmp(node a,node b)
{
    return a.r<b.r;
}
int cmp1(node a,node b)
{
    return a.idd<b.idd;
}
int pre[N],ans[N];
int main()
{
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	scanf("%d",&n);
	int q;
	scanf("%d",&q);
	for(int i = 1;i <= n;i++)
	{
		scanf("%d",&a[i]);
	}	
	for(int i = 1;i <= q;i++)
	{
		scanf("%d%d",&S[i].l,&S[i].r);
		S[i].idd=i;
	}
	sort(S+1,S+1+q,cmp);
	int tnum = 1;
    for(int i = 1;i<=n;i++)
    {
        if(tnum == q) break;
        for(int j = 1;j*j<=a[i];j++)
        {
            if(a[i]%j==0)
            {
                if(pre[j]!=0) add(pre[j],j);
                pre[j]=i;
                if (j*j==a[i]) continue ;
                if(pre[a[i]/j]!=0) add(pre[a[i]/j],a[i]/j);
                pre[a[i]/j]=i;
            }
        }
        while(tnum<=q&&S[tnum].r==i)
        {
            ans[S[tnum].idd]=getmax(S[tnum].l);
            tnum++;
        }
    }
    sort(S+1,S+1+q,cmp1);
    for(int i = 1;i <= q;i++)
    {
        /*if(S[i].l==S[i].r) printf("0\n");
        else*/ printf("%d\n",ans[i]);
    }
	return 0 ;
}

如果你们实在是看不懂我的题解，也看不懂我的标程的话，请见大佬博客：

大佬博客1