UVa 11235

　　题目大意：给出一个非降序排列的整数数组a[1...n]，对于一系列询问(i, j)，求出a_i到a_j中出现最多的次数。

　　由于数组是非降序的，可以把数组进行游程编码(Run Length Encoding, RLE)。什么是游程编码呢，比如序列1，1，1，2，2，3，可以编码成（1，3），（2，2），（3，1），其中（a，b）表示有b个连续的a。然后就是RMQ问题了，可以使用Sqare Table算法，预处理时间为O(nlogn)，每个查询只需O(1)。

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <climits>
  4 #define MAXN 100000+10
  5 using namespace std;
  6 
  7 int cnt[MAXN], num[MAXN], left[MAXN], right[MAXN];
  8 int d[MAXN][20];
  9 int n;
 10 int size;    // the size of cnt[]
 11 
 12 // read data and run length encoding
 13 void RLE()
 14 {
 15     int x, pre = INT_MAX;
 16     int cur = -1;    // the index of current segment
 17     int l;    // l is the left boundary of current segment
 18     for (int i = 0; i < n; i++)
 19     {
 20         scanf("%d", &x);
 21         if (x == pre)
 22         {
 23             cnt[cur]++;
 24             num[i] = cur;
 25             left[i] = l;
 26         }
 27         else
 28         {
 29             if (cur >= 0)
 30             {
 31                 // set the right boundary
 32                 for (int j = l; j <= i-1; j++)
 33                     right[j] = i-1;
 34             }
 35             cur++;
 36             l = i;
 37             num[i] = cur;
 38             left[i] = l;
 39             cnt[cur] = 1;
 40             pre = x;
 41         }
 42     }
 43     for (int i = l; i < n; i++)
 44         right[i] = n-1;
 45     size = cur + 1;
 46 }
 47 
 48 void RMQ_init()
 49 {
 50     int n = size;
 51     for (int i = 0; i < n; i++)
 52         d[i][0] = cnt[i];
 53     for (int j = 1; (1<<j) <= n; j++)
 54         for (int i = 0; i + (1<<j) - 1 < n; i++)
 55         {
 56             int t = i + (1<<(j-1));
 57             d[i][j] = max(d[i][j-1], d[t][j-1]);
 58         }
 59 }
 60 
 61 int RMQ(int L, int R)
 62 {
 63     if (L > R)   return 0;
 64     int k = 0;
 65     while (1<<(k+1) <= R-L+1)   k++;
 66     return max(d[L][k], d[R-(1<<k)+1][k]);
 67 }
 68 
 69 int main()
 70 {
 71 #ifdef LOCAL
 72     freopen("in", "r", stdin);
 73     //freopen("out", "w", stdout);
 74 #endif
 75     int q;
 76     while (scanf("%d%d", &n, &q) != EOF && n)
 77     {
 78         RLE();
 79         //for (int i = 0; i < size; i++)
 80         //    printf("%d ", cnt[i]);
 81         //printf("
");
 82         //for (int i = 0; i < n; i++)
 83         //    printf("%d	%d	%d
", num[i], left[i], right[i]);
 84         RMQ_init();
 85         while (q--)
 86         {
 87             int L, R;
 88             scanf("%d%d", &L, &R);
 89             L--;
 90             R--;
 91             if (num[L] == num[R])   printf("%d
", R-L+1);
 92             else
 93             {
 94                 int t1 = right[L]-L+1;
 95                 int t2 = R-left[R]+1;
 96                 int t3 = RMQ(num[L]+1, num[R]-1);
 97                 printf("%d
", max(t1, max(t2, t3)));
 98             }
 99         }
100     }
101     return 0;
102 }

View Code

　　代码中cnt[i]表示第i段中有多少个数，num[i]、left[i]、right[i]分别表示位置i所在段的编号和左右端点的位置。分别考虑L和R在同一段、相邻段和中间隔若干个段的情况。

　　刚开始的时候d[][]数组的第一维和第二维开得一样大，都是1000，RE了，以为开得不够大，扩大到10000，还是RE，然后就想难道要到100000，那样岂不是超出内存限制了？

然后看别人代码，d[maxn][20]...好吧，我没考虑第二维j的取值不可能太大，没考虑清楚啊