学步园

不是自己智商不够，而是自己不能钻进去，不能静下心来，学习新的知识点，其实这个信息竞赛和其他的竞赛也是一样的，知识点庞杂，所以自己一定要能够静下心来好好的学习。虽然不一定都能涉及到，但是自己一定要精心的学习真正的用脑子思考。

这道题目的意思是：给你N个非递减数列，然后任意给定范围，求得范围内出现最多的次数，并输出。这个题目看似简单，其实想清楚也是比较困难的。

要用到游程编码，这个具体的思想我也不清楚，但是看了题解的思路，我就自己捉摸去了，也不知道自己写的是不是和题解中的思想一致。

具体的思路是这样的，因为RMQ解决的问题是区间内的最大值和最小值的查询问题，那么很显然是要先把区间的出现的次数存起来准备用于RMQ的。然后就是要把每个相同的区域统一编号，每个区域的左边界和右边界也要存起来，这样就可以通过这些区域（块）描述出整个的数组了，有了这样的描述，那么解决问题也就及其的顺手了。

那么，取得的范围[a, b]首先判断a和b对应的是不是一个下标，如果是的话，那么答案直接就能得出，就是b-a+1；不是的话，那么就要分作三段来求了，左边的a到a所在块的右边界，右边的b到b的左边界，和中间的那一块。这样就可以得出答案了。

贴出代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

const int MAXN = 100000 + 11;

vector <int> cnt;

int N, M, A[MAXN];

int d[MAXN][18], L[MAXN], R[MAXN], num[MAXN];

void RMQ_init()
{
	int nc = cnt.size();
//	cout << "nc = " << nc << endl;
	for (int i = 0; i < nc; i++)
	{
		d[i + 1][0] = cnt[i];
//		cout << "cnt[i] = " << cnt[i] << endl;
	}
	for (int j = 1; (1 << j) <= nc; j++)
	{
		for (int i = 1; i + (1 << j) - 1 <= nc; i++)
		{
			d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int RMQ(int l, int r)
{
	if (l > r)
	{
		return 0;
	}
	int k = 0;
	while ((1 << (k + 1)) <= r - l + 1)
	{
		k++;
	}
	return max(d[l][k], d[r - (1 << k) + 1][k]);
}

int main()
{
	while (scanf("%d", &N) != EOF)
	{
		if (N == 0)
		{
			break;
		}
		scanf("%d", &M);
		int start = 1;
		int temp = 1;
		cnt.clear();
		for (int i = 1; i <= N; i++)
		{
			scanf("%d", &A[i]);
		}
		A[N + 1] = 1000000000;
		for (int i = 1; i <= N + 1; i++)
		{
			if (A[i] > A[i - 1])
			{
				cnt.push_back(i - start);
				L[temp] = start;
				R[temp] = i - 1;
				for (int j = start; j < i; j++)
				{
					num[j] = temp;
				}
				start = i;
				temp++;
			}
		}
		int a, b;
		RMQ_init();
		for (int i = 0; i < M; i++)
		{
			scanf("%d%d", &a, &b);
			if (num[a] == num[b])
			{
//				cout << "num_a = " << num[a] << endl;
//				cout << "num_b = " << num[b] << endl;
				printf("%d\n", b - a + 1);
			}
			else
			{
				int ans = 0;
//				cout << "num_a = " << num[a] << endl;
//				cout << "num_b = " << num[b] << endl;
//				cout << "R[a] = " << R[num[a]] << endl;
//				cout << "L[b] = " << L[num[b]] << endl;
				ans = max((R[num[a]] - a + 1), (b - L[num[b]] + 1));
//				cout << "ans1 = " << ans << endl;
				ans = max(ans, RMQ(num[a] + 1, num[b] - 1));
				printf("%d\n", ans);
			};
		
		}
		
	}
//	system("pause");
	return 0;
}