本文主要是介绍区间求最值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
//题解：先把1到1000000的因子全部打表出来，然后用线段树查询。
//标程：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int c = 1000010;
int dp[c], a[4*c], m;
inline int max(int x,int y){return x > y ? x : y;
}
void build(int n){int i, x;for(m = 1; m < n + 1; m *= 2); for(i = 1 + m; i <= n + m; ++ i){scanf("%d",&x);a[i] = dp[x];}for(i = m - 1; i > 0; -- i)a[i] = max(a[i*2],a[i*2+1]);
}
int query(int x,int y){ int ans=-1; for(x = x + m - 1, y = y + m + 1; y - x > 1; x /= 2, y /= 2){ //结束条件: y - x <= 1;if(x % 2 == 0) ans = max(ans, a[x^1]); if(y % 2 == 1) ans = max(ans,a[y^1]); //线段树下标是从1开始的，偶数就是左子树，而奇数就是右子树。} return ans;
}
int main(){
// freopen("a.txt","r",stdin);int t, i, n, j;memset(dp,0,sizeof(dp));for(i = 1; i < c; ++ i){for(j = i; j < c; j += i)dp[j] ++;}scanf("%d",&t);while(t --){memset(a,0,sizeof(a));scanf("%d",&n);build(n);int q, x, y;scanf("%d",&q);while(q --){cin >> x >> y;printf("%d\n",query(x, y));}}return 0;
}这篇关于区间求最值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
