首页 > 代码库 > 区间求最值 线段树

区间求最值 线段树

2024-07-07 19:45:12   228人阅读

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

区间求最值
 
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
用朴素线段树和st算法都超内存

zkw线段树：

参考：http://www.cnblogs.com/markliu/archive/2012/05/30/2527020.html

//20716KB	781ms
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define N 1000010
int T[N*4],M;
int yin[N];
void inti()
{
    int i,j;
    yin[1]=0;
    for(i=1;i<N;i++)
    {
        for(j=i;j<N;j+=i)yin[j]++;
    }
 //  for(i=0;i<100;i++)printf("%d %d\n",i,yin[i]);
}
void seg_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);
        T[i]=yin[x];
    }
    for(i=M-1;i;i--) T[i]=max(T[i*2],T[i*2+1]);
}

int seg_query(int s,int t){
    int maxc=-1;
    for(s=s+M-1,t=t+M+1;s^t^1;s/=2,t/=2){
        if(s%2==0) maxc=max(maxc,T[s^1]);
        if(t%2==1) maxc=max(maxc,T[t^1]);
    }
    return maxc;
}

int main()
{
    inti();
    int n,m,a,b;
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(T,0,sizeof(T));
        seg_build(n);
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&a,&b);
            printf("%d\n",seg_query(a,b));
        }
    }
    return 0;
}

网上题解，想不通为什么这个能过，还比我的省时间

参考：http://blog.csdn.net/u012964281/article/details/29578869

//8864KB	765ms
#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;
}


联系
我们