#include <stdio.h>
#define inf 0x7fffffff
#define N 50010
struct node
{
	int l, r;
	int min, max;
}node[N*4];

int num[N], nmax, nmin;
void creat(int t, int l, int r)
{
	node[t].l = l;
	node[t].r = r;
	node[t].min = inf;
	node[t].max = -inf;
	if(l == r - 1)
	{
		if(num[l] > num[r])
		{
			node[t].min = num[r];
			node[t].max = num[l];
		}
		else
		{
			node[t].min = num[l];
			node[t].max = num[r];
		}
		return;
	}
	int mid = (l + r) >> 1;
	creat(t << 1, l, mid);
	creat(t << 1 | 1, mid , r);
	node[t].min = node[t << 1].min < node[t << 1 | 1].min ? node[t << 1].min : node[t << 1 | 1].min;
	node[t].max = node[t << 1].max > node[t << 1 | 1].max ? node[t << 1].max : node[t << 1 | 1].max;
}
void query(int t, int l, int r)
{
	if(node[t].l >= l && node[t].r <= r)
	{
		nmax = node[t].max > nmax ? node[t].max : nmax;
		nmin = node[t].min < nmin ? node[t].min : nmin;
		return ;
	}
	if(node[t].l == node[t].r - 1)	return;
	int mid = (node[t].l + node[t].r) >> 1;
	if(l >= mid)
		query(t << 1 | 1, l, r);
	else if(r <= mid)
		query(t << 1, l, r);
	else
	{
		query(t << 1, l, mid);
		query(t << 1 | 1, mid, r);
	}
}
int main()
{
	int n, q, i;
	//freopen("data.in", "r", stdin);
	scanf("%d%d", &n, &q);
	for(i = 1; i <= n; i++)
		scanf("%d", &num[i]);
	creat(1, 1, n);
	while(q--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		if(x == y)
		{
			printf("0\n");
			continue;
		}
		nmax = -inf; nmin = inf;
		query(1, x, y);
		printf("%d\n", nmax - nmin);
	}
	return 0;
}

• 我也是1A水过，2S+ (3) lijingwei 2012-01-18 16:38:05
  • Re:我也是1A水过，2S+ (24) dgsrz 2012-07-01 10:52:12
    • Re:我也是1A水过，2S+ (43) chenxuan123456789 2012-09-13 12:12:32
• 构造两颗线段树，时间就少点，我没有做任何优化就1.5秒，那些250ms大牛是怎么写的？ (1501) hujk2008 2012-09-18 22:07:55
• 两棵ZKW线段树1400ms。。。 (8) HTwood 2013-01-09 20:00:26
  • Re:两棵ZKW线段树1400ms。。。 (27) wy54224 2013-02-24 19:23:00