训练指南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的最大值
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int Max = + ;
int n, m, tot;
int num[Max], Right[Max], Left[Max], cnt[Max];
int dp[Max][];
//dp[i][j] 表示 i 段开始长度为2^j长度的区间
void RMQ_init()
{
memset(dp, , sizeof(dp));
for (int i = ; i <= tot; i++)
dp[i][] = cnt[i];
for (int j = ; ( << j) <= n; j++) // 这里的长度 是 n 是整个区间内的全部元素，
{
for (int i = ; i + ( << j) - <= tot; i++) //
{
dp[i][j] = max(dp[i][j - ], dp[i + ( << (j - )) ][j - ]);
}
}
}
int RMQ(int l, int r)
{
if (l > r)
return ;
int k = ;
while ( << (k + ) <= (r - l + ))
k++;
return max(dp[l][k], dp[r - ( << k) + ][k]);
}
int main()
{
while (scanf("%d", &n) != EOF && n)
{
scanf("%d", &m);
memset(num, , sizeof(num));
memset(Right, , sizeof(Right));
memset(Left, , sizeof(Left));
memset(cnt, , sizeof(cnt));
int temp, last = INF;
tot = ;
for (int i = ; i <= n; i++)
{
scanf("%d", &temp);
if (temp == last) // 如果与前面的数相等
{
num[i] = tot; // 当前位置的段号不变
Right[tot]++; //当前段的右边的位置+1,
cnt[tot]++; //当前段的元素个数+1
}
else //如果不与前面的数相等则开启一个新的段
{
num[i] = ++tot; // 段号++,
cnt[tot]++;
Left[tot] = Right[tot] = i; // 当前段的左右端点都是i
last = temp; // 记录一下当前的元素
}
}
RMQ_init();
int l, r;
while (m--)
{
scanf("%d%d", &l, &r);
if (num[l] == num[r])
{
printf("%d\n", r - l + );
continue;
}
printf("%d\n", max(RMQ(num[l] + , num[r] - ), max(Right[ num[l] ] - l + , r - Left[ num[r] ] + )));
}
}
return ;
}