2331799_ac_1996ms_644k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

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

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

	scanf("%ld%ld",&n,&q);
	for(i = 0; i < n; i++)
		scanf("%ld",&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("%ld%ld",&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("%ld\n",Max-Min);
		}
	}
	return 1;
}