UVA 11235 - Requent values - RMQ (st 표) + 여정 인 코딩

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23846
이 문제 의 데이터 에서 ST 표 와 선분 수 는 모두 100 + ms 의 차이 가 크 지 않다. 

    ：
             a，            (i, j)，  ai,ai+1...aj               。

예비 처 리 는 먼저 모든 같은 요 소 를 하나의 node 로 합 치 는 것 입 니 다. node 는 이 요소 번호 + 이 요소 개 수 를 포함 합 니 다. (표 2 라 고 함)
그리고 위치 기록 i 에 대응 하 는 것 은 예비 처리 후의 i 번 째 node 입 니 다.
매번 조회 (a, b)
a, b 위치 만 대응 해 야 합 니 다. 표 2 의 번호 사이 의 모든 node 는 이 node 의 요소 갯 수 에 대해 RMQ 를 구하 고 tmp 1 로 기록 합 니 다.
그리고 a 에 대응 하 는 node 의 오른쪽 점 - a + 1 ,tmp 2 (즉, 원소 값 이 a 인 계산 가능 한 개수)
같은 이치  대응 하 는 node  b - 왼쪽 점 + 1, tmp 3 로 기록 (즉, 원소 값 이 b 인 계산 가능 한 개수)
삼자 가 최대 를 취하 면 된다
특수 한 경우 a, b 에 대응 하 는 node 가 같은 경우 b - a + 1 만 출력 하면 됩 니 다.

 
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std; 
#include <iostream>
using namespace std; 

const int maxn=100005;
int ok;//ok      
 
 int value [maxn],cun[maxn];// i   ，       
 int l[maxn],r[maxn];// i                
 int who[maxn];//        i    
 int tm[maxn]; //    

 int mx[maxn][16];//16 logn   ，st 
 
int max(int a,int b)
{
	if (a<b)
	return b;
	return a;
}  
 void rmq_init()
 {
     int i,j;
     for(j=1;j<=ok;j++) mx[j][0]=cun[j];
     int m=floor(log((double)ok)/log(2.0));
     for(i=1;i<=m;i++){
         for(j=ok;j>0;j--){
             mx[j][i]=mx[j][i-1];
             if(j+(1<<(i-1))<=ok) mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
         }
    }
   
 }
 
 int rmq_max(int l,int r)
 {
     int m=floor(log((double)(r-l+1))/log(2.0));
    int a=max(mx[l][m],mx[r-(1<<m)+1][m]); 
    return a;   //a    
 } 


int main()
{ 
    int  t;
	int  n,m; 
	while (cin>>n)
	{
	
		if (!n) break;
				
		scanf("%d",&m); 
		memset(mx,0,sizeof(mx));

		int  i;
		for(  i = 1; i <= n; i++)
		{
			scanf("%d",&tm[i]); 
		} 
		 ok=0;
			for(  i = 1; i <= n; i++)
		{
			value[++ok]=tm[i];
			cun[ok]=1;
			who[i]=ok;
			l[ok]=i;
			while(tm[i+1]==tm[i])
			{
			
				cun[ok]++;
				i++;
				who[i]=ok;
			} 	
			r[ok]=i;
		} 
		rmq_init(); 
		int a,b;
	 	for(  i = 1; i <= m; i++)
		{
			scanf("%d%d",&a,&b); 
			int t1=who[a];  //t a        
			int t2=who[b];
			int tmp1=0;
			if (t2>t1+1)	//      1                  ，   0
				 tmp1=rmq_max(t1+1,t2-1); 

			int tmp2=r[t1]-a+1;//a      
			int tmp3=b-l[t2]+1;
			if (t2==t1)		//  a,b     ，     ，  b-a+1
			printf("%d
",b-a+1);
		else
			printf("%d
",max(tmp1,max(tmp2,tmp3)));

		} 
			
			
	}   
    
    
    return 0;
}