2337774_ac_808ms_632k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 62 行

#include <stdio.h>

int h[50001];
int max[50001], min[50001];

int main()
{
	int Max, Min;
	int l, r;
	int i, j, n, q;

	scanf("%d%d",&n,&q);
	for(i = 0; i < n; i++)
		scanf("%d",&h[i]);
	max[0] = min[0] = -1;
	for(i = 1; i < n; i++)
	{
		j = i-1;
		while(j>=0&&h[j]>h[i])
			j = min[j];
		min[i] = j;
		j = i-1;
		while(j>=0&&h[j]<h[i])
			j = max[j];
		max[i] = j;
	}
	for(i = 0; i < q; i++)
	{
		scanf("%d%d",&l,&r);
		l--,r--;
		if(l==r)
			printf("0\n");
		else
		{
			j = r;
			while(1)
			{
				if(max[j]<l)
				{
					Max = h[j];
					break;
				}
				else
					j = max[j];
			}
			j = r;
			while(1)
			{
				if(min[j]<l)
				{
					Min = h[j];
					break;
				}
				else
					j = min[j];
			}
			printf("%d\n",Max-Min);
		}
	}
	return 1;
}