第三行有一个整数q(1<=q<=10^5)，代表有q个询问，接下来每一行有两个整数。l_i,r_i(l_i<=r_i,l_i>=1,r_i<=N).代表数组的一段区间,而且l_i+1>=l_i,r_i+1>=r_i。

1

10

2 3 5 6 9 11 12 36 39 44

3

2 6

3 8

3 9

4

9

9

HUNNU Contest 

http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11460

这题感觉非常巧妙，首先学到了怎么把给定范围因子数打表，然后 怎么减少时间复杂度。

假设打表后每次直接在给定范围内比較出最大值是会超时的，可是我们能够把前一次比較出来的最大值下标赋值出来，下次查找的话。直接从这个下标開始。会节约非常多时间。

#include <cstdio>

#include <cstring>

#define maxn 1000005

int find[maxn];

int num[maxn];

int main()

{

	memset(find, 0, sizeof(find));//把 maxn范围内数的因子数打表

	for (int i = 1; i < maxn; i++){

		for (int j = i; j < maxn; j += i) //每次加i就等于j扩大一倍，两倍。三倍，，。。，

			find[j]++;

	}

	int t;

	scanf("%d", &t);

	while (t--)

	{

		int n, q;

		scanf("%d", &n);

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

		{

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

			//intf("%d\n",find[num[i]]);

		}

		scanf("%d", &q);

		int a, b, ans = -1;

		int aa, bb, sign;

		scanf("%d%d", &a, &b);

		aa = a, bb = b;

		for (int i = a; i <= b; i++) //先比較出第一组的最大值 保存下标

			if (ans < find[num[i]]){

				ans = find[num[i]];

				sign = i;

			}

		printf("%d\n", ans);

		--q;  //注意

		while (q--)

		{

			scanf("%d%d", &a, &b);

			if (sign >= aa&&sign <= a){   //假设上一次的下标在aa和a之间。那仅仅能从a開始

				ans = -1;

				for (int i = a; i <= b; i++)

				if (ans < find[num[i]]){

					ans = find[num[i]];

					sign = i;

				}

			}

			else     //否则直接从bb開始，由于else的话 sign仅仅能是大于a。所以能够直接从bb開始。

			{

				for (int i = bb; i <= b; i++)

				if (ans < find[num[i]]){

					ans = find[num[i]];

					sign = i;

				}

			}

			aa = a, bb = b;

			printf("%d\n", ans);

		}

	}

	return 0;

}