训练指南P198
题意：给出一个非降序排列的整数数组a1, a2…… an,你的任务是对于一系列询问（i，j)，回答ai, ai+1 ……aj 中出现的次数最多的次数
这题不仅学到了rmq的应用还学到了游程编码
对于一组数 -1， 1， 1， 2， 2， 2， 4就可以编码成(-1, 1), (1, 2), (2, 3), (4, 1)，其中（a, b）表示 b 个连续的 a，cnt[i]表示第 i 段中数出现的次数。num[p] 表示p位置的数所在的段的标号， left[p]表示p位置的数所在段的左边那个数的下标， right[p]表示p位置的数所在段的右边那个数的下标。
那么对于查询（L, R)的结果就是下面三个中的最大的 从 L 到 L 所在段的结束出的元素（right[l] - l + 1）这里都是与L处的数相等的，然后从r所在的段开始到r处的元素的个数（ r - left[r] + 1) 都是与r处相等的，然后还有中间的 （num[l] + 1, num[r] - 1）段的cnt的最大值
1 #include <cstring> 2 #include <algorithm> 3 #include <cstdio> 4 #include <string.h> 5 #include <iostream> 6 using namespace std; 7 const int INF = 0x3f3f3f3f; 8 const int Max = 100000 + 10; 9 int n, m, tot; 10 int num[Max], Right[Max], Left[Max], cnt[Max]; 11 int dp[Max][32]; 12 //dp[i][j] 表示 i 段开始长度为2^j长度的区间 13 void RMQ_init() 14 { 15 memset(dp, 0, sizeof(dp)); 16 for (int i = 1; i <= tot; i++) 17 dp[i][0] = cnt[i]; 18 for (int j = 1; (1 << j) <= n; j++) // 这里的长度 是 n 是整个区间内的全部元素， 19 { 20 for (int i = 1; i + (1 << j) - 1 <= tot; i++) // 21 { 22 dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1)) ][j - 1]); 23 } 24 } 25 } 26 int RMQ(int l, int r) 27 { 28 if (l > r) 29 return 0; 30 int k = 0; 31 while (1 << (k + 1) <= (r - l + 1)) 32 k++; 33 return max(dp[l][k], dp[r - (1 << k) + 1][k]); 34 } 35 int main() 36 { 37 while (scanf("%d", &n) != EOF && n) 38 { 39 scanf("%d", &m); 40 memset(num, 0, sizeof(num)); 41 memset(Right, 0, sizeof(Right)); 42 memset(Left, 0, sizeof(Left)); 43 memset(cnt, 0, sizeof(cnt)); 44 int temp, last = INF; 45 tot = 0; 46 for (int i = 1; i <= n; i++) 47 { 48 scanf("%d", &temp); 49 if (temp == last) // 如果与前面的数相等 50 { 51 num[i] = tot; // 当前位置的段号不变 52 Right[tot]++; //当前段的右边的位置+1, 53 cnt[tot]++; //当前段的元素个数+1 54 } 55 else //如果不与前面的数相等则开启一个新的段 56 { 57 num[i] = ++tot; // 段号++, 58 cnt[tot]++; 59 Left[tot] = Right[tot] = i; // 当前段的左右端点都是i 60 last = temp; // 记录一下当前的元素 61 } 62 } 63 RMQ_init(); 64 int l, r; 65 while (m--) 66 { 67 scanf("%d%d", &l, &r); 68 if (num[l] == num[r]) 69 { 70 printf("%d ", r - l + 1); 71 continue; 72 } 73 printf("%d ", max(RMQ(num[l] + 1, num[r] - 1), max(Right[ num[l] ] - l + 1, r - Left[ num[r] ] + 1))); 74 } 75 } 76 return 0; 77 }