uva 11235 - Frequent values(RMQ)

uva 11235 - Frequent values(RMQ)

題目鏈接：uva 11235 - Frequent values

題目大意：給定一個非降序的整數數組，要求計算對於一些詢問(i,j)，回答ai,ai+1,…,aj中出現最多的數出現的次數。

解題思路：因為序列為非降序的，所以相同的數字肯定是靠在一起的，所以用o(n)的方法處理處每段相同數字的區間。然後對於每次詢問：

• num[i]=num[j]:j?i+1
• numi≠numj:max(RMQ(righti+1,reftj?1),max(righti?i+1,j?leftj+1))

  #include 
  #include 
  #include 
  
  using namespace std;
  const int maxn = 1e5+5;
  
  int N, Q, num[maxn], rmq[maxn][20];
  int left[maxn], right[maxn];
  
  void RMQ_init () {
      memset(rmq, 0, sizeof(rmq));
      for (int i = 1; i <= N; i++)
          rmq[i][0] = right[i] - left[i] + 1;
  
      for (int j = 1; (1<= 1; i--) {
          if (num[i] == num[i+1])
              right[i] = right[i+1];
          else
              right[i] = i;
      }
      RMQ_init();
  }
  
  int RMQ (int L, int R) {
      if (L > R)
          return 0;
      int k = 0;
      while (1<<(k+1) <= R-L+1)
          k++;
      return max(rmq[L][k], rmq[R-(1<