hunnu 11460 - 구간 최대 값 구하 기 (선분 트 리 템 플 릿)

제목 링크: 전송 문
구간 값 구하 기
Time Limit: 3000ms, Special Time Limit:7500ms, Memory Limit:32768KB
Total submit users: 83, Accepted users: 60
Problem 11460 : No special judgement
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

문제 풀이 사고: 먼저 시 계 를 쳐 서 1000000 이내 의 매개 수의 인자 개 수 를 구 한 다음 에 선분 수 는 구간 의 최대 치 를 구하 고 RMQ 로 메모 리 를 폭발 시 킵 니 다.

#include   
#include   
#include   
#include   
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;  
typedef __int64  ll;
const int N = 1000008;
const int M = 5007;
const int INF = 0x3fffffff;
const int mod = 1e9+7;
const double Pi = acos(-1.0);
const double sm = 1e-9;

int rec[N<<2];//Sum  ，Add        
int A[N];//        [1,n] 

//PushUp         ，       
void PushUp(int rt){rec[rt]=max(rec[rt<<1],rec[rt<<1|1]);}  
//Build       
void Build(int l,int r,int rt){ //l,r        ，rt          
	if(l==r) {//         
		rec[rt]=A[l];//        
		return;  
	}  
	int m=(l+r)>>1;  
	//       
	Build(l,m,rt<<1);  
	Build(m+1,r,rt<<1|1);  
	//       
	PushUp(rt);  
}  

int Query(int L,int R,int l,int r,int rt){//L,R      ，l,r        ，rt          
	if(L <= l && r <= R){  
		//    ，       
		return rec[rt];  
	}  
	int m=(l+r)>>1;  

	//      
	int ANS=0;  
	if(L <= m) ANS=max(ANS,Query(L,R,l,m,rt<<1));  
	if(R >  m) ANS=max(ANS,Query(L,R,m+1,r,rt<<1|1));  
	return ANS;  
}   

int num[N];
void getNumDivisor( int n )
{

	fill( num , num+N , 0 );
	for( int i = 1 ; i*i < n ; ++i ){
		for( int j = i ; i*j < n ; ++j ){
			num[i*j] += 2;
			if( i == j ) num[i*j]--;
		}
	}
}

int main()
{
	getNumDivisor(N);
	int T,n,m,a,b;
	scanf("%d",&T);
	while( T-- ){
		scanf("%d",&n);
		for( int i = 1 ; i <= n ; ++i ){
			scanf("%d",&a);
			A[i] = num[a];
		}
		Build(1,n,1);
		scanf("%d",&m);
		for( int i = 0 ; i < m ; ++i ){
			scanf("%d%d",&a,&b);
			printf("%d
",Query(a,b,1,n,1));
		}
	}
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

hunnu 11460 - 구간 최대 값 구하 기 (선분 트 리 템 플 릿)

Problem 11460 : No special judgement 길이 가 N 인 배열 을 지정 하고 q 개의 질문 이 있 습 니 다. 모든 질문 은 배열 의 한 구간 에서 그 요소 의 인자 의 개수 가 가장 큽 니...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hunnu 11460 - 구간 최대 값 구하 기 (선분 트 리 템 플 릿)

좋은 웹페이지 즐겨찾기