离散化后rmq，新白书上对这个题有讲解。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 #define N  100000 7 int p[N]; 8 int dp[22][N+1]; 9 int hash[3*N];10 int que[N+1];11 int L[N+1];12 int R[N+1];13 int o[N+1];14 void init_rmq(int n)15 {16     int i,j;17     for(i = 1;i <= n;i ++)18     dp[0][i] = o[i];19     for(i = 1;(1<
         
          <= n;i ++)20     {21         for(j = 1;j + (1<<(i-1)) <= n;j ++)22         {23             dp[i][j] = max(dp[i-1][j],dp[i-1][j+(1<<(i-1))]);24         }25     }26 }27 int rmq(int x,int y)28 {29     if(x > y) return 0;30     int k = log(y-x+1.0)/log(2.0);31     return max(dp[k][x],dp[k][y-(1<
          
           <= n;i ++)52 {53 scanf("%d",&p[i]);54 }55 L[1] = 1;56 num = 1;57 temp = 1;58 hash[p[1]+N] = 1;59 for(i = 2;i <= n;i ++)60 {61 if(p[i] != p[i-1])62 {63 R[num] = i-1;64 o[num] = temp;65 hash[p[i-1]+N] = num;66 temp = 1;67 num ++;68 L[num] = i;69 }70 else71 {72 temp ++;73 }74 }75 R[num] = i-1;76 o[num] = temp;77 hash[p[i-1]+N] = num;78 init_rmq(num);79 while(m--)80 {81 scanf("%d%d",&x,&y);82 printf("%d\n",query(x,y));83 }84 }85 return 0;86 }