1.题目描述：点击打开链接
2.解题思路：本题属于RMQ问题。注意到整个数组是非降序的，，所有相等的元素都会聚在一起，这样就可以把整个数组进行游程编码（RunLengh Encodeing RLE）。比如-1,1,2,2,2,4就可以表示为(-1,1),(1,2),(2,3),(4,1)。其中(a,b)表示有b个连续的a。本题中，用Left[pos],Right[pos]分别表示位置pos所在段的左右端点的位置。p[i]表示第i段的元素个数。那么每次查询(L,R)的结果为以下三部分的最大值：从L到Right[L]处的元素个数，从Left[R]到R的元素个数，区间Right[L]+1到Left[R]-1之间的最大值，其中这段区间可以利用Sparse-table算法解决。特殊情况：如果L和R在同一段，那么答案就是R-L+1。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 100000+10int A[N];int n, q, e;int C[N][20], Left[N], Right[N];int p[N];void init(){for (int i = 0; i < n; i++)C[i][0] = p[i];for (int j = 1; (1 << j) <= n;j++)for (int i = 0; i + (1 << j) < n; i++)C[i][j] = max(C[i][j – 1], C[i + (1 << j – 1)][j – 1]);}int Query(int L, int R){int k = log((double)R – L + 1) / log(2.0);return max(C[L][k], C[R – (1 << k) + 1][k]);}int main(){//freopen("t.txt", "r", stdin);while (~scanf("%d", &n) && n){scanf("%d", &q);for (int i = 0; i < n; i++)scanf("%d", A + i);memset(p, 0, sizeof(p));int pos = 0;Left[0] = 0, p[0] = 1;for (int i = 1; i < n; i++){if (A[i] == A[i – 1])p[i] = p[i – 1] + 1;//数组p统计每段的个数，先进行累加，最后分别以每段最后的统计结果为准，进行统一else{pos = i;p[i] = 1;}Left[i] = pos;}pos = n – 1, Right[pos] = pos;for (int i = n – 2; i >= 0; i–){if (A[i] == A[i + 1])p[i] = p[i + 1];//以每段的最后一个数为准，将个数统一else pos = i;Right[i] = pos;}init();while (q–){int s, t;scanf("%d%d", &s, &t);s–, t–;int ans = 0;if (A[s] == A[t])ans = t – s + 1;//特殊情况else{if (Right[s] + 1 < Left[t] – 1)//三段的最大值ans = Query(Right[s] + 1, Left[t] – 1);ans = max(ans, Right[s] – s + 1);ans = max(ans, t – Left[t] + 1);}printf("%d\n", ans);}}return 0;}
即使是不成熟的尝试，也胜于胎死腹中的策略。
