首页 > 代码库 > 湖南师范大学 11460 区间求最值

湖南师范大学 11460 区间求最值

2024-07-07 17:07:48   225人阅读

区间求最值
 
Problem description
  给定一个长度为N 的数组，有q个询问，每个询问是求在数组的一段区间内那个元素的因子的个数最大，比如24的因子的个数就是8。 
Input
  首先是一个整数t，表示有t组测试数据，每组测试数据的第一行是一个整数N(1<=N<=10^6),第二行有N个整数ai(1<=ai<=10^6,i=1,2,.....N)表示数组的元素。第三行有一个整数q(1<=q<=10^5)，代表有q个询问，接下来每一行有两个整数，li,ri(li<=ri,li>=1,ri<=N).代表数组的一段区间,并且li+1>=li,ri+1>=ri。
Output
  对于每组数据的每个询问都输出一个整数表示在这段区间里面元素因子个数的最大值。
Sample Input
1
10
2 3 5 6 9 11 12 36 39 44
3
2 6
3 8
3 9
Sample Output
4
9
9
Problem Source

代码：

#include <cstdio>
#include <cstring>
#define maxn 1000005
int find[maxn];
int num[maxn];
int main()
{
	memset(find, 0, sizeof(find));
	for (int i = 1; i < maxn; i++){
		for (int j = i; j < maxn; j += i)
			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]);
		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){
				ans = -1;
				for (int i = a; i <= b; i++)
				if (ans < find[num[i]]){
					ans = find[num[i]];
					sign = i;
				}
			}
			else
			{
				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;
}


联系
我们