HDU 1806 && POJ 3368 Frequent values (RMQ)

시비 가 내 려 간 이상 같은 점 은 모두 한데 모여 같은 점 을 한 단락 으로 나 누 었 을 것 이다.그 다음 에 각 단락 의 길 이 를 기록 하고 가장 오른쪽 끝 과 가장 왼쪽 끝 을 기록 한 다음 에 원래 수열 에 있 는 모든 위치 에서 어느 단락 에 속 하 는 레이 블 을 기록 합 니 다.그리고 모든 질문 에 대해 3 부분 으로 나 누 어 각 부분 을 계산 한 다음 에 이 세 부분 에 대해 최대 치 를 취 할 수 있다.코드 는 다음 과 같 습 니 다:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL long long
#define PI acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
int dp[110000][30], sum[110000], num[110000], lef[110000], righ[110000], cnt, a[110000];
void rmq()
{
        int i, j;
        for(i=1;i<=cnt;i++){
                dp[i][0]=sum[i];
        }
        for(j=1;(1<<j)<=cnt;j++){
                for(i=1;i<=cnt-(1<<j)+1;i++){
                        dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
                }
        }
}
int query(int l, int r)
{
        if(l>r) return 0;
        int k=0;
        while((1<<k+1)<=r-l+1) k++;
        return max(dp[l][k],dp[r+1-(1<<k)][k]);
}
int main()
{
        int n, q, i, l, r, j;
        while(scanf("%d",&n)!=EOF&&n){
                scanf("%d",&q);
                for(i=1;i<=n;i++){
                        scanf("%d",&a[i]);
                }
                cnt=1;
                sum[1]=1;
                num[1]=1;
                lef[1]=righ[1]=1;
                for(i=2;i<=n;i++){
                        if(a[i]!=a[i-1]){
                                sum[++cnt]=1;
                                lef[cnt]=righ[cnt]=i;
                        }
                        else{
                                sum[cnt]++;
                                righ[cnt]=i;
                        }
                        num[i]=cnt;
                }
                rmq();
                while(q--){
                        scanf("%d%d",&l,&r);
                        if(num[l]==num[r]){
                                printf("%d
",r-l+1);
                                continue ;
                        }
                        int ll=num[l], rr=num[r];
                        int x=sum[ll]-l+lef[ll];
                        int y=sum[rr]-righ[rr]+r;
                        printf("%d
",max(max(x,y),query(num[righ[ll]+1],num[lef[rr]-1])));
                }
        }
        return 0;
}